/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 115ms 147.27 MiB
#2 Accepted 113ms 147.242 MiB
#3 Accepted 185ms 147.52 MiB
#4 Accepted 174ms 147.562 MiB
#5 Accepted 190ms 147.867 MiB
#6 Accepted 190ms 147.77 MiB
#7 Accepted 197ms 148.996 MiB
#8 Accepted 217ms 149.02 MiB
#9 Accepted 209ms 149.02 MiB
#10 Accepted 221ms 151.426 MiB
#11 Accepted 207ms 151.672 MiB
#12 Accepted 208ms 151.504 MiB
#13 Accepted 201ms 149.02 MiB
#14 Accepted 182ms 148.012 MiB
#15 Accepted 194ms 147.602 MiB
#16 Accepted 187ms 147.52 MiB
#17 Accepted 214ms 147.758 MiB
#18 Accepted 383ms 147.535 MiB
#19 Accepted 389ms 148.02 MiB
#20 Accepted 411ms 149.723 MiB
#21 Accepted 485ms 153.441 MiB
#22 Accepted 495ms 153.309 MiB
#23 Accepted 194ms 148.977 MiB
#24 Accepted 279ms 155.141 MiB
#25 Accepted 1192ms 148.848 MiB
#26 Accepted 414ms 147.684 MiB
#27 Time Exceeded ≥1609ms ≥148.996 MiB

Code



#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl "\n"
#define FF ios_base::sync_with_stdio(0);cin.tie(0)
#define binary(value, size) cout << bitset<size>(value) << '\n'
#define Tp template<class T>
#define Tpp template<typename T>
#define Tppp template<typename T1,typename T2>
#define eps 1e-9
#define pf printf
#define sf scanf
#define clr(arr,val) memset((arr),val,(sizeof(arr)))
#define rep(i,a,b) for(long long int i=a;i<b;i++)
#define repb(i,a,b) for(long long int i=a;i>=b;i--)
#define all(v) (v).begin(),(v).end()
#define asort(a) sort(a.begin(),a.end())
#define arev(a) reverse(a.begin(),a.end())
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define pbb pop_back
#define mp make_pair
#define V vector
#define P pair
#define M map
#define mt make_tuple
#define BS(v,x) binary_search(v.begin(),v.end(),x) //return true /false
#define LB(v,x) lower_bound(v.begin(),v.end(),x)-v.begin()//found and that value and not found than greater value pos
#define UB(v,x) upper_bound(v.begin(),v.end(),x)-v.begin() //found and greater value pos && not found also greater pos
#define sma(c) towlower(c)
#define rt(x) sqrt(x)
#define cap(c) towupper(c)
#define sq(a) ((a)*(a))
#define cube(a) ((a)*(a)*(a))
#define SUM(v) accumulate (v.begin(),v.end(),0)//sum of the vector
#define MAX(v) *max_element(v.begin(),v.end())//max element of the vector
#define MIN(v) *min_element(v.begin(),v.end())//min element of the vector
#define SZ(x) long long int(x.size())
#define Ceil(n) (long long int)ceil(n)
#define Floor(n) (long long int)floor(n)
#define deb(x) cout << #x << " = " << x << "\n";
#define deb2(x,y)  cout << #x << " = " << x << ", "; cout << #y << " = " << y << "\n";
#define deb3(x,y,z) cout << #x << " = " << x << ", "; cout << #y << " = " << y << ", "; cout << #z << " = " << z << "\n";
#define deb4(x,y,z,r) cout << #x << " = " << x << ", "; cout << #y << " = " << y << ", "; cout << #z << " = " << z << ", ";cout << #r << " = " << r << "\n";
#define out(ans) cout<<ans<<"\n"
#define outs(ans) cout<<ans<<" "<<"\n"
#define FI freopen ("in.txt", "r", stdin)
#define FO freopen ("out.txt", "w", stdout)

using namespace std;
//using namespace __gnu_pbds;

typedef int ll;
typedef double lf;
typedef long double llf;
typedef unsigned long long int ull;
typedef vector<ll> vll;
typedef vector<vector<ll> > v2d;
typedef vector<vector<vector<ll> > > v3d;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef map<ll,ll> mpl;
typedef priority_queue<ll> heap;// heap max value from top
typedef priority_queue<ll, vector<ll>, greater<ll> > revheap;//heap min value from top

bool Check(int N,int pos)
{
    return (bool)(N & (1<<pos));
}
int Set(int N,int pos)
{
    return N=N | (1<<pos);
}

const int mx=1e5+10;
int status[(mx/32)+2];
ll N=mx;
vll primes;
void sieve()
{

	 memset(status,0,sizeof(status));
	 int i, j, sqrtN;
     sqrtN = int( sqrt( N ) );
     for( i = 3; i <= sqrtN; i += 2 )
     {
		 if( Check(status[i>>5],i&31)==0)
		 {
	 		 for(j = i*i; j <= N; j += (i<<1) )
			 {
				 status[j>>5]=Set(status[j>>5],j & 31)   ;
	 		 }
		 }
	 }
	 primes.pb(2);

	 for(i=3;i<=N;i+=2)
        if( Check(status[i>>5],i&31)==0) primes.pb(i);
     //deb(primes.size());
}


vector<ll> mm[3200010],vali[3200010];
map<ll,ll> haire;
ll pp,r;

void factorize(ll idx,ll n )
{

    //vll factors;
    ll sqrtn = sqrt ( n );

    //deb(n);
    for ( ll i = 0; i <r  && primes[i] <= sqrtn; i++ )
    {
        if ( n % primes[i] == 0 )
        {
            ll xg=0;
            while ( n % primes[i] == 0 )
            {
                xg++;
                n /= primes[i];
                //freq[primes[i]]++;
            }
            ll kk=haire[primes[i]];
            if(kk==0)
            {
                pp++;
                mm[pp].clear();
                vali[pp].clear();
                haire[primes[i]]=pp;
                kk=pp;
            }


            ll last;
            if(mm[kk].empty()) last=0;
            else last=vali[kk].back();

            vali[kk].pb(last+xg);
            mm[kk].pb(idx);
            //deb2(primes[i],xg);
            //factors.pb(primes[i]);
            sqrtn = sqrt ( n );
        }
    }
    if ( n != 1 )
    {
        ll kk=haire[n];
        if(kk==0)
        {
            pp++;
            mm[pp].clear();
            vali[pp].clear();
            haire[n]=pp;
            kk=pp;
        }


         ll last;
         if(mm[kk].empty()) last=0;
         else last=vali[kk].back();
         mm[kk].pb(idx);
         vali[kk].pb(last+1);
    }
//    ll q=factors.size();
//    for(ll i=0;i<q;i++)
//    {
//        if(i!=q-1)cout<<factors[i]<<"^"<<freq[factors[i]]<<" ";
//        else cout<<factors[i]<<"^"<<freq[factors[i]];
//    }
//    cout<<endl;
}
vpll temp;
void factorize2(ll n)
{

    //vll factors;
    //vpll temp;
    ll sqrtn =(ll) sqrt ( n );

    for ( ll i = 0; i <r  && primes[i] <= sqrtn; i++ )
    {
        if ( n % primes[i] == 0 )
        {            ll xx=0;
            while ( n % primes[i] == 0 )
            {
                xx++;
                n /= primes[i];
                //freq[primes[i]]++;
            }
            temp.pb({primes[i],xx});
            //temp[{primes[i],xx}].pb(i);
            //factors.pb(primes[i]);
            sqrtn =sqrt ( n );
        }
    }
    if ( n != 1 )
    {
        temp.pb({n,1});
    }
    //return temp;
//    ll q=factors.size();
//    for(ll i=0;i<q;i++)
//    {
//        if(i!=q-1)cout<<factors[i]<<"^"<<freq[factors[i]]<<" ";
//        else cout<<factors[i]<<"^"<<freq[factors[i]];
//    }
//    cout<<endl;
}

void S()
{
   pp=0;

   haire.clear();
   temp.clear();

   ll n,x;cin>>n>>x;
   vll v(n);
   rep(i,0,n)
   {
       cin>>v[i];factorize(i,v[i]);
   }


   //cout<<"check->";for(auto xx:haire) cout<<xx.F<<" "<<xx.S<<endl;cout<<endl;
   //return;
   ll q;cin>>q;
   factorize2(x);
   vpll temp2;
   for(auto xx:temp)
   {
        temp2.pb({haire[xx.F],xx.S});
   }
   //return;
   //return;
   rep(i,0,q)
   {
       ll left,right;cin>>left>>right;
       left--;right--;
       //return;
       bool ff=1;
       for(auto xx:temp2)
       {
           //deb2(xx.F,xx.S);
           //return;

           auto it=lower_bound(all(mm[xx.F]),left);
           auto it2=upper_bound(all(mm[xx.F]),right);
           if(it2==mm[xx.F].begin())
           {
               //cout<<"1\n";
               ff=0;break;
           }


           ll baad=0;

           if(it==mm[xx.F].begin())
           {
               baad=0;
           }
           else
           {
               it--;
               ll pos=it-mm[xx.F].begin();
               baad=vali[xx.F][pos];
           }
           it2--;
           ll ase;
           ll pos2=it2-mm[xx.F].begin();
           //deb(pos2);
           if(pos2>=0) ase=vali[xx.F][pos2]-baad;

           else
           {
               //cout<<"2\n";
               ff=0;break;
           }
           //deb(pos);
           if(ase<xx.S)
           {
               //deb2(vali[gps][pos2],baad);
               //cout<<"3\n";cout<<xx.F<<" "<<xx.S<<endl;deb(ase);
               ff=0;break;
           }
       }
       if(ff) cout<<"Yes\n";
       else cout<<"No\n";


   }

}

int main()
{
    FF;
    sieve();
    r=primes.size();
    ll tc;cin>>tc;
    while(tc--)
    {
        S();
    }
    return 0;
}


Information

Submit By
Type
Submission
Problem
P1128 Roy and Product
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 16:53:53
Judged At
2024-11-05 16:53:53
Judged By
Score
97
Total Time
≥1609ms
Peak Memory
≥155.141 MiB