Submission #970806

#	Time	Username	Problem	Language	Result	Execution time	Memory
970806		lmaobruh	Sum Zero (RMI20_sumzero)	C++14	61 / 100	328 ms	29792 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 4e5 + 5;

int n, q, nxt[N], ku[N][10];
map<ll, int> mp;

void build_rmq() {
  for (int i = 1; i <= n; ++i) ku[i][0] = nxt[i];
  int cur, ti;
  for (int j = 1; j <= 9; ++j)
    for (int i = 1; i + (1 << (j * 2)) - 1 <= n; ++i) {
    	cur = i;
      for (int ti = 1; ti <= 4; ++ti) {
        cur = ku[cur][j - 1];
        if (cur == 0) break;
        else cur++;
      }
      if (cur == 0) {
        ku[i][j] = 0;
        continue;
      }
      ku[i][j] = cur - 1;
    }
}

void build() {
  cin >> n;
  ll sum = 0, x;
  mp[0] = 0;
  for (int i = 1; i <= n; ++i) nxt[i] = -1;
  for (int i = 1; i <= n; ++i) {
    cin >> x;
    sum += x;
    if (mp.count(sum)) nxt[mp[sum] + 1] = i;
    mp[sum] = i;
  }
  mp.clear();
  int pre = -1;
  for (int i = n; i >= 1; --i) {
    if (nxt[i] != -1) pre = (pre == -1 ? nxt[i] : min(pre, nxt[i]));
    else nxt[i] = 0;
    nxt[i] = (pre != -1 ? pre : 0);
  }
  build_rmq();
}

int ans;
int que(int l, int r) {
	ans = 0;
  for (int i = 9; i >= 0; --i)
    while (ku[l][i] != 0 && ku[l][i] <= r) {
      ans += 1 << (i * 2);
      l = ku[l][i] + 1;
    }
  return ans;
}

void ouput() {
  cin >> q;
  while (q--) {
    static int l, r; cin >> l >> r;
    cout << que(l, r) << '\n';
  }
}

void solve() {
  build();
  ouput();
}

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  solve();
  return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'void build_rmq()':
sumzero.cpp:12:12: warning: unused variable 'ti' [-Wunused-variable]
   12 |   int cur, ti;
      |            ^~

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