Submission #970914

#	Time	Username	Problem	Language	Result	Execution time	Memory
970914		lmaobruh	Sum Zero (RMI20_sumzero)	C++14	61 / 100	383 ms	22100 KiB

sumzero

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

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

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

void build_rmq() {
  int cur, ti;
  for (int j = 1; j <= 5; ++j)
    for (int i = 1; i + (1 << (j * 2)) - 1 <= n; ++i) {
    	cur = i;
      for (int ti = 1; ti <= 16; ++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) ku[i][0] = -1;
  for (int i = 1; i <= n; ++i) {
    cin >> x;
    sum += x;
    if (mp.count(sum)) ku[mp[sum] + 1][0] = i;
    mp[sum] = i;
  }
  mp.clear();
  int pre = -1;
  for (int i = n; i >= 1; --i) {
    if (ku[i][0] != -1) pre = (pre == -1 ? ku[i][0] : min(pre, ku[i][0]));
    else ku[i][0] = 0;
    ku[i][0] = (pre != -1 ? pre : 0);
  }
  build_rmq();
}

int ans;
int que(int l, int r) {
	ans = 0;
  for (int i = 4; i >= 0; --i)
    while (ku[l][i] != 0 && ku[l][i] <= r) {
      ans += 1 << (i * 4);
      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:11:12: warning: unused variable 'ti' [-Wunused-variable]
   11 |   int cur, ti;
      |            ^~

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