/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 580.0 KiB
#2 Accepted 5ms 688.0 KiB
#3 Time Exceeded ≥1587ms ≥1016.0 KiB
#4 Time Exceeded ≥1594ms ≥1004.0 KiB

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);

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)
{
    if(start == end)
    {
        sg[node] = doit(a[start]);
        return;
    }
    int mid = (start+end)/2;
    buildsg(node*2,start,mid,a,sg);
    buildsg(node*2+1,mid+1,end,a,sg);
    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);

    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:46:40
Judged At
2024-11-11 02:33:33
Judged By
Score
3
Total Time
≥1594ms
Peak Memory
≥1016.0 KiB