Submission #1171906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171906		fryingduc	Sum Zero (RMI20_sumzero)	C++20	61 / 100	285 ms	48672 KiB

sumzero

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 4e5 + 5;
const int LG = 19;
int n, a[maxn];
long long prf[maxn];
int nxt[maxn];
map<long long, int> mp;
int up[maxn][LG + 1];

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    prf[i] = prf[i - 1] + a[i];
  }
  up[n + 1][0] = n + 2;
  up[n + 2][0] = n + 2;
  for (int i = n; i; --i) {
    mp[prf[i]] = i;
    if (mp.count(prf[i - 1])) {
      up[i][0] = mp[prf[i - 1]] + 1;
    } else {
      up[i][0] = n + 2;
    }
  }
  for (int i = n; i; --i) {
    up[i][0] = min(up[i][0], up[i + 1][0]);
  }
  for (int i = 1; i <= LG; ++i) {
    for (int u = 1; u <= n + 2; ++u) {
      up[u][i] = up[up[u][i - 1]][i - 1];
    }
  }
  int q; cin >> q;
  while (q--) {
    int l, r; cin >> l >> r;
    int res = 0;
    for (int i = LG; i >= 0; --i) {
      if (up[l][i] <= r + 1) {
        res ^= (1 << i);
        l = up[l][i];
      }
    }
    cout << res << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0; 
}

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 0 / 39