fork download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long ll;
  5. typedef pair<ll,ll> pll;
  6. typedef pair<int, int> pii;
  7. typedef pair<ll,pll> lll;
  8. #define fi first
  9. #define se second
  10. void maxi (ll &x, ll y) {x = max (x, y);}
  11. void mini (ll &x, ll y) {x = min (x, y);}
  12.  
  13. const ll maxN = 4e5 + 5, maxLog = 20, mod = 1e9 + 7, inf64 = 1e13, maxK = 5;
  14.  
  15. struct Edge {ll u, v, w;};
  16.  
  17. struct Dsu {
  18.     ll pr [maxN];
  19.     void init (ll x) {
  20.         for (int i = 1; i <= x; i ++) pr [i] = i;
  21.     }
  22.     ll fin (ll x) {
  23.         if (x == pr [x]) return x;
  24.         return pr [x] = fin (pr [x]);
  25.     }
  26.     bool merge (ll x, ll y) {
  27.         x = fin (x);
  28.         y = fin (y);
  29.         if (x == y) return 0;
  30.         pr [x] = y;
  31.         return 1;
  32.     }
  33. };
  34.  
  35. ll n, w, a [maxN], ne [maxN] [maxLog], sum [maxN], q;
  36. map <ll, ll> mp;
  37.  
  38. signed main () {
  39.     ios::sync_with_stdio (0);
  40.     cin. tie (0);
  41.     cout. tie (0);
  42.     #define task "sum0"
  43.     if (fopen (task".inp", "r")) {
  44.         freopen (task".inp", "r", stdin);
  45.         freopen (task".out", "w", stdout);
  46.     }
  47.     cin >> n;
  48.     for (int i = 1; i <= n; i ++) {
  49.         cin >> a [i];
  50.         sum [i] = sum [i - 1] + a [i];
  51.     }
  52.     ne [n + 1] [0] = n + 1;
  53.     for (int i = n; ~i; i --) {
  54.         if (mp [sum [i]] == 0) ne [i] [0] = ne [i + 1] [0];
  55.         else ne [i] [0] = min (ne [i + 1] [0], mp [sum [i]]);
  56.         mp [sum [i]] = i;
  57.     }
  58.     for (int i = n + 1; ~i; i --) for (int j = 1; j < maxLog; j ++) ne [i] [j] = ne [ne [i] [j - 1]] [j - 1];
  59.     cin >> q;
  60.     for (int i = 1, l, r; i <= q; i ++) {
  61.         cin >> l >> r;
  62.         l --;
  63.         ll cnt = 0;
  64.         for (int j = maxLog - 1; ~j; j --) if (ne [l] [j] <= r) {
  65.             cnt += (1 << j);
  66.             l = ne [l] [j];
  67.         }
  68.         cout << cnt << '\n';
  69.     }
  70. }
  71.  
Success #stdin #stdout 0.01s 5672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JkgD8Z
language:
C++14 (gcc 8.3)
created:
6 days 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!