Submission #970804

#	Time	Username	Problem	Language	Result	Execution time	Memory
970804		lmaobruh	Sum Zero (RMI20_sumzero)	C++14	61 / 100	378 ms	50204 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][19];
map<ll, int> mp;

void build_rmq() {
  for (int i = 1; i <= n; ++i) ku[i][0] = nxt[i];
  for (int j = 1; j <= 18; ++j)
    for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
      if (ku[i][j - 1] == 0) {
        ku[i][j] = 0;
        continue;
      }
      ku[i][j] = ku[ku[i][j - 1] + 1][j - 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 que(int l, int r) {
  int ans = 0;
  for (int i = 18; i >= 0; --i)
    if (l + (1 << i) - 1 <= n && ku[l][i] != 0 && ku[l][i] <= r) {
      // dbg(l, i, ku[l][i]);
      ans += 1 << i;
      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);
  int tc = 1; // cin >> tc;
  for (; tc; --tc) solve();
  return 0;
}

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