Submission #52130024

---

Source Code Expand

#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<cassert>
#include<random>
#include<set>
#include<map>
#include<cassert>
#include<unordered_map>
#include<bitset>
#include<numeric>
#include<algorithm>
using namespace std;
typedef long long ll;
const int inf=1<<30;
const ll INF=1LL<<62;
typedef pair<int,int> P;
typedef pair<int,P> PP; 


vector<P> divisor(ll n){
    map<ll,ll> mp;

    for(ll d=2;d*d<=n;d++){
        ll cnt=0;
        while(n%d==0){
            n/=d;
            cnt++;
        }
        cnt%=3;
        if(cnt>0){
            mp[d]+=cnt;
        }   
    }

    if(n>1){
        mp[n]++;
        n/=n;
    }

    vector<P> res;

    for(auto [val,num]:mp){
        res.emplace_back(val,num);
    }
    return res;
}

int main(){
    int N,Q;
    cin>>N>>Q;
    vector<ll> A(N);
    vector<vector<P>> cnt(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
        cnt[i]=divisor(A[i]);
    }

    /*
    for(int i=0;i<N;i++){
        cout<<"i="<<i<<endl;
        for(auto [v,num]:cnt[i]){
            cout<<"v="<<v<<",num="<<num<<endl;
        }
    }
    */


    vector<P> ranges;
    vector<int> L(Q),R(Q);
    for(int q=0;q<Q;q++){
        cin>>L[q]>>R[q];
        L[q]--;
        //[L[q],R[q])
        ranges.emplace_back(L[q],R[q]);
    }
    vector<int> order(Q);
    iota(order.begin(),order.end(),0);

    const int D=max((int)sqrt(2*N),1);

    sort(order.begin(),order.end(),
    [&](const int i,const int j){
        int ri=R[i]/D;
        int rj=R[j]/D;
        if(ri!=rj){
            return ri<rj;
        }else{
            return L[i]<L[j];
        }
    });

    const int MAXA=1000000;
    vector<int> counter(MAXA+1,0);


    bool flag=true;

    int cnt_cubic=0;

    auto add=[&](int idx){
        //idxの追加
        for(auto [val,num]:cnt[idx]){

            int pre=counter[val];
            counter[val]+=num;
            counter[val]%=3;
            if(pre==0 && counter[val]>0){
                cnt_cubic++;
            }
            else if(pre>0 && counter[val]==0){
                cnt_cubic--;
            }
        }

    };

    auto del=[&](int idx){
        //idxの削除
        for(auto [val,num]:cnt[idx]){

            int pre=counter[val];
            counter[val]-=num;
            counter[val]+=3;
            counter[val]%=3;

            if(pre==0 && counter[val]>0){
                cnt_cubic++;
            }
            else if(pre>0 && counter[val]==0){
                cnt_cubic--;
            }
        }

    };

    vector<bool> ans(Q);
    
    
    
    int left=0,right=0;

    for(int q=0;q<Q;q++){
        //cout<<"ord["<<q<<"]="<<order[q]<<endl;
        //[nl,nr)
        int nl=L[order[q]],nr=R[order[q]];

        while(nl<left){
            //今見ている先のleft(つまりleft-1)を含ませる
            left--;
            add(left);
        }

        while(left<nl){
            del(left);
            left++;
        }

        while(nr<right){
            right--;
            del(right);
        }

        while(right<nr){
            add(right);
            right++;
        }


        ans[order[q]]=(cnt_cubic==0);
    
    }

    for(int q=0;q<Q;q++){
        cout<<(ans[q]?"Yes":"No")<<endl;
    }

    
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:98:10: warning: unused variable ‘flag’ [-Wunused-variable]
   98 |     bool flag=true;
      |          ^~~~

Judge Result