fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cmath>
  5. #include <map>
  6.  
  7. using namespace std;
  8.  
  9. struct BIT {
  10.   struct Foo {
  11.     long long s0 = 0;
  12.     int s1 = 0;
  13.   };
  14.   vector<Foo> dat;
  15.  
  16.   BIT(int n) : dat(n + 1) {}
  17.  
  18.   void update0(int k, long long v) {
  19.     for (int i = k + 1; i < dat.size(); i += i & -i) {
  20.       dat[i].s0 -= k * v;
  21.       dat[i].s1 += v;
  22.     }
  23.   }
  24.  
  25.   long long query0(int k) {
  26.     long long res0 = 0;
  27.     long long res1 = 0;
  28.     for (int i = k; i > 0; i -= i & -i) {
  29.       res0 += dat[i].s0;
  30.       res1 += dat[i].s1;
  31.     }
  32.     return res0 + res1 * k;
  33.   }
  34.  
  35.   void update(int l, int r, long long v) {
  36.     update0(l, v);
  37.     update0(r, -v);
  38.   }
  39.  
  40.   long long query(int l, int r) {
  41.     return query0(r) - query0(l);
  42.   }
  43. };
  44.  
  45. bool is_square(int n) {
  46.   int s = sqrt(n);
  47.   return s * s == n;
  48. }
  49.  
  50. int main() {
  51.   int T;
  52.   cin >> T;
  53.   while (T--) {
  54.     int n, q;
  55.     cin >> n >> q;
  56.     vector<int> a(n);
  57.     for (int i = 0; i < n; i++) {
  58.       scanf("%d", &a[i]);
  59.     }
  60.     vector<int> ls(q), rs(q);
  61.     vector<vector<int>> es(n + 1);
  62.     for (int i = 0; i < q; i++) {
  63.       scanf("%d %d", &ls[i], &rs[i]);
  64.       ls[i]--;
  65.       es[rs[i]].push_back(i);
  66.     }
  67.     vector<long long> ans(q);
  68.     vector<pair<int, int>> vs;
  69.     vector<pair<int, int>> us;
  70.     BIT bit(n + 1);
  71.     for (int i = 0; i < n; i++) {
  72.       us.clear();
  73.       for (auto p : vs) {
  74.         int nv = p.first & a[i];
  75.         if (us.empty() || us.back().first != nv) {
  76.           us.emplace_back(nv, p.second);
  77.         }
  78.       }
  79.       if (us.empty() || us.back().first != a[i]) {
  80.         us.emplace_back(a[i], i);
  81.       }
  82.       swap(us, vs);
  83.       for (int j = 0; j < vs.size(); j++) {
  84.         if (is_square(vs[j].first)) {
  85.           if (j + 1 < vs.size()) {
  86.             bit.update(vs[j].second, vs[j + 1].second, 1);
  87.           } else {
  88.             bit.update(vs[j].second, i + 1, 1);
  89.           }
  90.         }
  91.       }
  92.       for (int j : es[i + 1]) {
  93.         ans[j] = bit.query(ls[j], i + 1);
  94.       }
  95.     }
  96.     for (int i = 0; i < q; i++) {
  97.       printf("%lld\n", ans[i]);
  98.     }
  99.   }
  100. }
Runtime error #stdin #stdout #stderr 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/H1eQ6R
language:
C++14 (gcc 8.3)
created:
5 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!