fork download
copy 
  1. // www.hackerearth.com/challenge/competitive/airtel-crack-the-code/algorithm/square-and-cube-2-dd08d321/
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. const int MAX_VAL = 1e5 + 5;
  7. const int MAX_N = 3e5 + 5;
  8.  
  9. const int BASE = 100003;
  10. const long long MOD = 1e9 + 7;
  11.  
  12. int N, Q, A[MAX_N];
  13. int cnt2[MAX_VAL], cnt3[MAX_VAL];
  14. int zero[MAX_N], neg[MAX_N];
  15. long long basepow[MAX_VAL], hash2[MAX_N], hash3[MAX_N];
  16.  
  17. int lp[MAX_VAL];
  18. vector<int> pr;
  19. vector<int> p2[MAX_VAL];
  20. vector<pair<int, int> > p3[MAX_VAL];
  21. void init() {
  22.     for (int i = 2; i < MAX_VAL; i++) {
  23.         if (lp[i] == 0) lp[i] = i, pr.push_back(i);
  24.         for (int j = 0; j < pr.size() && pr[j] <= lp[i] && i * pr[j] < MAX_VAL; j++)
  25.             lp[i * pr[j]] = pr[j];
  26.         int j = i;
  27.         while (j != 1) {
  28.             int cur = lp[j], cnt = 0;
  29.             while (lp[j] == cur)
  30.                 j /= lp[j], cnt++;
  31.             if (cnt & 1) p2[i].push_back(cur);
  32.             if (cnt % 3) p3[i].emplace_back(cur, cnt % 3);
  33.         }
  34.     }
  35.     basepow[0] = 1;
  36.     for (int i = 1; i < MAX_VAL; i++)
  37.         basepow[i] = (basepow[i - 1] * BASE) % MOD;
  38. }
  39.  
  40. void solve() {
  41.     for (int i = 1; i <= N; i++) {
  42.         zero[i] = zero[i - 1];
  43.         neg[i] = neg[i - 1];
  44.         hash2[i] = hash2[i - 1];
  45.         hash3[i] = hash3[i - 1];
  46.         if (A[i] == 0)
  47.             zero[i]++;
  48.         if (A[i] < 0) {
  49.             neg[i]++;
  50.             A[i] = -A[i];
  51.         }
  52.         for (int p : p2[A[i]]) {
  53.             hash2[i] = (hash2[i] - cnt2[p] * basepow[p]) % MOD;
  54.             cnt2[p] ^= 1;
  55.             hash2[i] = (hash2[i] + MOD + cnt2[p] * basepow[p]) % MOD;
  56.         }
  57.         for (auto &x : p3[A[i]]) {
  58.             int p, c; tie(p, c) = x;
  59.             hash3[i] = (hash3[i] - cnt3[p] * basepow[p]) % MOD;
  60.             cnt3[p] += c; cnt3[p] %= 3;
  61.             hash3[i] = (hash3[i] + MOD + cnt3[p] * basepow[p]) % MOD;
  62.         }
  63.     }
  64. }
  65.  
  66. int main() {
  67.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  68.     init();
  69.  
  70.     cin >> N >> Q;
  71.     for(int i = 1; i <= N; i++)
  72.         cin >> A[i];
  73.  
  74.     solve();
  75.  
  76.     for(int i = 0; i < Q; i++) {
  77.         int L, R; cin >> L >> R;
  78.         int z, n, c2, c3;
  79.         z = zero[R] - zero[L - 1];
  80.         n = neg[R] - neg[L - 1];
  81.         c2 = hash2[R] - hash2[L - 1];
  82.         c3 = hash3[R] - hash3[L - 1];
  83.         int ans = (!c3) << 1 | (!c2 && !(n & 1));
  84.         if (z) ans = 3;
  85.  
  86.         if (ans == 0) cout << "None";
  87.         else if (ans == 1) cout << "Square";
  88.         else if (ans == 2) cout << "Cube";
  89.         else cout << "Both";
  90.         cout << "\n";
  91.     }
  92.  
  93.     return 0;
  94. }
Success #stdin #stdout 0.04s 15840KB
comments (?)
stdin
copy 
7 5
2 4 16 -4 5 5 7
1 2
2 3
3 4
5 6
6 7
stdout
copy 
Cube
Both
Cube
Square
None
https://ideone.com/GLRp6J
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!