Submission #1171910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171910		fryingduc	Sum Zero (RMI20_sumzero)	C++20	100 / 100	839 ms	21544 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 = 8;
int n;
long long prf[maxn];
int ord[maxn];
int up[maxn][LG + 1];

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    int x; cin >> x;
    prf[i] = prf[i - 1] + x;
    ord[i] = i;
  }
  sort(ord, ord + n + 1, [](const int &x, const int &y) -> bool {
    return (prf[x] != prf[y] ? prf[x] < prf[y] : x < y);
  });
  up[n + 1][0] = n + 2;
  up[n + 2][0] = n + 2;
  for (int i = 1; i <= n; ++i) up[i][0] = n + 2;
  for (int i = 0; i <= n; ++i) {
    int cur = 0;
    while (i + cur <= n and prf[ord[i]] == prf[ord[i + cur]]) {
      ++cur;
    }
    for (int j = i + 1; j < i + cur; ++j) {
      up[ord[j - 1] + 1][0] = min(up[ord[j - 1] + 1][0], ord[j] + 1);
    }
    i = i + cur - 1;
  }
  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 l, r;
  int res;
  int q; cin >> q;
  while (q--) {
    cin >> l >> r;
    res = 0;
    while (up[l][LG] <= r + 1) {
      res += (1 << LG);
      l = up[l][LG];
    }
    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: 39 / 39