fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4.  
  5. void scanint(int &x)
  6. {
  7.     register int c = gc();
  8.     x = 0;
  9.     int neg = 0;
  10.     for(;((c<48 || c>57) && c != '-');c = gc());
  11.     if(c=='-') {neg=1;c=gc();}
  12.     for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
  13.     if(neg) x=-x;
  14. }
  15. int n,q,l=0,r=0;
  16. int a[300000];
  17. int qorder[300000];
  18. pair <int,int> query[300000];
  19. int ans[300000];
  20. int nextp[100001];
  21. int atable[100001]= {0};
  22. int lpf[100001],lpfpow[100001],lpfcnt[100001];
  23. int cnt=1;
  24. int b1;
  25. int pr,neg,sq,cb,z;
  26. int compare(const void *a,const void *b)
  27. {
  28.     int x=*(int *)a,y=*(int *)b;
  29.     if(query[x].first/b1!=query[y].first/b1)
  30.         return query[x].first/b1-query[y].first/b1;
  31.     return query[x].second-query[y].second;
  32. }
  33.  
  34. void init(void)
  35. {
  36.     for(int i=0; i<=100000; i++)
  37.     {
  38.         lpf[i]=i;
  39.         lpfpow[i]=1;
  40.         lpfcnt[i]=0;
  41.     }
  42.     for(int i=2; i<=100000; i++)
  43.     {
  44.         if(lpf[i]==i)
  45.         {
  46.             lpfpow[i]=i;
  47.             lpfcnt[i]=1;
  48.             for(int j=2*i; j<=100000; j+=i)
  49.             {
  50.                 if(i<lpf[j])
  51.                 {
  52.                     int y=j;
  53.                     lpf[j]=i;
  54.                     lpfcnt[j]=0;
  55.                     lpfpow[j]=1;
  56.                     while(y%i==0)
  57.                     {
  58.                         y/=i;
  59.                         lpfcnt[j]++;
  60.                         lpfpow[j]*=i;
  61.                     }
  62.                 }
  63.             }
  64.         }
  65.     }
  66.     for(int i=2;i<=100000;i++)
  67.     {
  68.         nextp[i]=i/lpfpow[i];
  69.     }
  70. }
  71.  
  72. void add(int pos)
  73. {
  74.   //  cout << "add : ";
  75.  //   cout << pos << endl;
  76.     int prm,cnt;
  77.     int val=a[pos];
  78.  //   cout << val << endl;
  79.   //  cout << pr << " " << neg << " " << sq << " " << cb << endl;
  80.     if(val==0)
  81.         z++;
  82.     if(val<0)
  83.     {
  84.         val=-val;
  85.         neg++;
  86.     }
  87.     while(val>1)
  88.     {
  89.        // cout << "val is " << val << endl;
  90.         prm=lpf[val];
  91.         cnt=lpfcnt[val];
  92.         if(atable[prm]==0)
  93.         {
  94.             atable[prm]+=cnt;
  95.             val=nextp[val];
  96.             pr++;
  97.             if(atable[prm]%2==0)
  98.                 sq++;
  99.             if(atable[prm]%3==0)
  100.                 cb++;
  101.             continue;
  102.  
  103.         }
  104.         if(atable[prm]%2==0&&(atable[prm]+cnt)%2!=0)
  105.             sq--;
  106.         else if(atable[prm]%2!=0&&(atable[prm]+cnt)%2==0)
  107.             sq++;
  108.         if(atable[prm]%3==0&&(atable[prm]+cnt)%3!=0)
  109.             cb--;
  110.         else if(atable[prm]%3!=0&&(atable[prm]+cnt)%3==0)
  111.             cb++;
  112.         atable[prm]+=cnt;
  113.         val=nextp[val];
  114.     }
  115.   //  cout << pr << " " << neg << " " << sq << " " << cb << endl;
  116. }
  117.  
  118. void del(int pos)
  119. {
  120.   //  cout << "del : ";
  121.   //  cout << pos << endl;
  122.     int prm,cnt;
  123.     int val=a[pos];
  124.    // cout << pr << " " << neg << " " << sq << " " << cb << endl;
  125.     if(val==0)
  126.         z--;
  127.     if(val<0)
  128.     {
  129.         val=-val;
  130.         neg--;
  131.     }
  132.     while(val>1)
  133.     {
  134.         prm=lpf[val];
  135.         cnt=lpfcnt[val];
  136.         if(atable[prm]==cnt)
  137.         {
  138.             pr--;
  139.             val=nextp[val];
  140.             if(atable[prm]%2==0)
  141.                 sq--;
  142.             if(atable[prm]%3==0)
  143.                 cb--;
  144.             atable[prm]-=cnt;
  145.             continue;
  146.         }
  147.         if(atable[prm]%2==0&&(atable[prm]-cnt)%2!=0)
  148.             sq--;
  149.         else if(atable[prm]%2!=0&&(atable[prm]-cnt)%2==0)
  150.             sq++;
  151.         if(atable[prm]%3==0&&(atable[prm]-cnt)%3!=0)
  152.             cb--;
  153.         else if(atable[prm]%3!=0&&(atable[prm]-cnt)%3==0)
  154.             cb++;
  155.         atable[prm]-=cnt;
  156.         val=nextp[val];
  157.     }
  158.   //  cout << pr << " " << neg << " " << sq << " " << cb << endl;
  159. }
  160.  
  161. int main()
  162. {
  163.     init();
  164.     cin >> n >> q;
  165.     for(int i=0; i<n; i++)
  166.         scanint(a[i]);
  167.     b1=sqrt(n);
  168.     for(int i=0; i<q; i++)
  169.     {
  170.         scanint(query[i].first);
  171.         scanint(query[i].second);
  172.         qorder[i]=i;
  173.     }
  174.     pr=sq=neg=cb=z=0;
  175.     add(0);
  176.     qsort(qorder,q,sizeof(int),compare);
  177.     for(int i=0; i<q; i++)
  178.     {
  179.         int ql=query[qorder[i]].first-1;
  180.         int qr=query[qorder[i]].second-1;
  181.         while(l<ql)
  182.         {
  183.             del(l);
  184.             l++;
  185.         }
  186.         while(l>ql)
  187.         {
  188.             l--;
  189.             add(l);
  190.         }
  191.         while(r<qr)
  192.         {
  193.             r++;
  194.             add(r);
  195.         }
  196.         while(r>qr)
  197.         {
  198.             del(r);
  199.             r--;
  200.         }
  201.         if(z>0)
  202.             ans[qorder[i]]=1;
  203.         else if(neg%2)
  204.         {
  205.             if(cb==pr)
  206.                 ans[qorder[i]]=3;
  207.             else
  208.                 ans[qorder[i]]=4;
  209.         }
  210.         else
  211.         {
  212.             if(sq==pr&&cb==pr)
  213.                 ans[qorder[i]]=1;
  214.             else if(sq==pr)
  215.                 ans[qorder[i]]=2;
  216.             else if(cb==pr)
  217.                 ans[qorder[i]]=3;
  218.             else
  219.                 ans[qorder[i]]=4;
  220.         }
  221.      //   cout << qorder[i] << endl;
  222.      //   cout << pr << " " << neg << " " << sq << " " << cb << endl;
  223.     }
  224.     for(int i=0; i<q; i++)
  225.     {
  226.         if(ans[i]==1)
  227.             printf("Both\n");
  228.         else if(ans[i]==2)
  229.             printf("Square\n");
  230.         else if(ans[i]==3)
  231.             printf("Cube\n");
  232.         else
  233.             printf("None\n");
  234.     }
  235.     return 0;
  236. }
Success #stdin #stdout 0.01s 4508KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/k4qd3q
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!