/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 540.0 KiB
#2 Accepted 3ms 588.0 KiB
#3 Accepted 988ms 1020.0 KiB
#4 Accepted 977ms 1.211 MiB
#5 Time Exceeded ≥1599ms ≥1.59 MiB
#6 Time Exceeded ≥1599ms ≥1.449 MiB

Code

/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using minheap = priority_queue<long long, vector<long long>, greater<long long>>;
typedef tree<int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key

#define ll long long
#define ld long double
#define MOD 1000000007
#define pie 2*(acos(0.0))
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
#define endl '\n'
#define lcm(a,b) (a*b)/(__gcd<ll>(a,b))
#define print(v) for(auto e:v) cout<<e<<" "; cout<<endl;
#define printp(v) for(auto e:v) cout<<e.first<<" "<<e.second<<endl;
#define srt(v) sort(v.begin(),v.end())
#define rsrt(v) sort(v.rbegin(),v.rend())
#define life_is_a_race ios::sync_with_stdio(false); cin.tie(nullptr);
#define map unordered_map
bool notprime[100006];
vector<ll>allprime;
void seive()
{
    for(int i=2;i<=1000;i++)
    {
        if(notprime[i]) continue;
        for(int j=i+i;j<=100000;j+=i) notprime[j]=true;
    }
    for(int i=2;i<=32000;i++) {if(!notprime[i]) allprime.push_back(i);}
}


map<int,int> doit(int x)
{
    map<int,int> mp;
    for(auto e:allprime)
    {
        if(e>x) break;
        while(x%e==0)
        {
            mp[e]++;
            x /= e;
        }
    }
    if(x > 1) mp[x]++;
    return mp;
}
int n,x;

void combine(map<int,int>&m, map<int,int>&m1,map<int,int>&m2)
{
    for(auto e:m1) m[e.first]+= e.second;
    for(auto e:m2) m[e.first]+= e.second;
}

void buildsg(int node,int start,int end,vector<int>&a,vector<map<int,int>>&sg,map<int,int>&mx)
{
    if(start == end)
    {
        map<int,int> mm = doit(a[start]);
        for(auto e:mm) 
        {
            if(mx[e.first]) sg[node][e.first] += e.second;
        }
        return;
    }
    int mid = (start+end)/2;
    buildsg(node*2,start,mid,a,sg,mx);
    buildsg(node*2+1,mid+1,end,a,sg,mx);
    combine(sg[node],sg[node*2],sg[node*2+1]);
}

map<int,int> query(int node,int start,int end,int l,int r,vector<map<int,int>>&sg)
{
    map<int,int> m;
    if(l>end || r<start) return m;
    if(l<=start && r>=end) return sg[node];
    int mid = (start+end)/2;
    auto m1 = query(node*2,start,mid,l,r,sg);
    auto m2 = query(node*2+1,mid+1,end,l,r,sg);
    combine(m,m1,m2);
    return m;
}

void solve(int tc)
{
    //cout<<"Case "<<tc<<": ";
    cin >> n >> x;
    vector<int> a(n+1);
    for(int i=0;i<n;i++) cin>>a[i];
    
    map<int,int> mx = doit(x);
    
    vector<map<int,int>> sg(4*n+5);

    buildsg(1,0,n-1,a,sg,mx);

    int q; cin>>q; while(q--)
    {
        int l,r; cin>>l>>r;
        auto m = query(1,0,n-1,l-1,r-1,sg);
        bool ok = true;
        
        for(auto e:mx)
        {
            if(m[e.first] < e.second) 
            {
                ok = false;
                break;
            }
        }
        if(ok) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}
int main()
{
    life_is_a_race
    int t=1; 
    cin>>t;
    seive();
    
    for(int i=1;i<=t;i++) solve(i);
}

Information

Submit By
Type
Submission
Problem
P1128 Roy and Product
Contest
Lockout contest round-1 ( Mazharul Islam vs Thakur Emon)
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-04 17:54:31
Judged At
2024-11-04 17:54:31
Judged By
Score
7
Total Time
≥1599ms
Peak Memory
≥1.59 MiB