Submission #467966

#	Time	Username	Problem	Language	Result	Execution time	Memory
467966		MilosMilutinovic	Sum Zero (RMI20_sumzero)	C++14	0 / 100	9 ms	8268 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 4e5 + 5;
const int BASE = 32;
const int L32 = 5;

int n, a[N];
int pw[L32];
int nxt[N][L32];

vector <ll> xs;

void add(ll x) {
  xs.push_back(x);
}

int get(int x) {
  return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
}

void init() {
  pw[0] = 1;
  for (int i = 1; i < L32; i++)
    pw[i] = pw[i - 1] * 32;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < L32; j++)
      nxt[i][j] = N - 1;
  ll sum = 0;
  add(sum);
  for (int i = n - 1; i >= 0; i--) {
    sum += a[i];
    add(sum);
  }
  sum = 0;
  vector <int> last(xs.size() + 1, N - 1);
  last[get(sum)] = n;
  for (int i = n - 1; i >= 0; i--) {
    sum += a[i];
    nxt[i][0] = last[get(sum)];
    last[get(sum)] = i;
  }
  for (int i = n - 2; i >= 0; i--) {
    nxt[i][0] = min(nxt[i][0], nxt[i + 1][0]);
  }
  for (int j = 1; j < L32; j++) {
    for (int i = 0; i < n; i++) {
      int x = i;
      for (int k = 0; k < BASE; k++) {
        x = nxt[x][j - 1];
      }
      nxt[i][j] = x;
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  init();
  int qq;
  cin >> qq;
  while (qq--) {
    int l, r;
    cin >> l >> r;
    --l;
    int x = L32 - 1;
    int ans = 0;
    while (x >= 0) {
      if (nxt[l][x] <= r) {
        ans += pw[x];
        l = nxt[l][x];
      } else {
        x--;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

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