oj.uz

Submission #682879

# Submission time Handle Problem Language Result Execution time Memory
682879 2023-01-17T07:02:28 Z MilosMilutinovic Sum Zero (RMI20_sumzero) C++14
100 / 100
 706 ms 17428 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX = 400000;
const int L = 3;

int n;
int R[MAX];
int pw[L + 1];
int pos[MAX][L];
int i;

unordered_map<long long, int> mp;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> R[i];
  }
  long long s = 0;
  mp[0] = n;
  for (i = n - 1; i >= 0; i--) {
    s += R[i];
    if (mp.count(s)) {
      R[i] = mp[s] - 1;
    } else {
      R[i] = n;
    }
    mp[s] = i;
    if (i + 1 < n) {
      R[i] = min(R[i], R[i + 1]);
    }
  }
  mp.clear();
  pw[0] = 64;
  for (int i = 1; i < L; i++) {
    pw[i] = pw[i - 1] * 64;
  }
  int j, x, iter;
  for (i = 0; i < n; i++) {
    x = R[i];
    for (j = 0; j < 63; j++) {
      if (x + 1 < n) {
        x = R[x + 1];
      } else {
        x = n;
      }
    }
    pos[i][0] = x;
  }
  for (j = 1; j < L; j++) {
    for (i = 0; i < n; i++) {
      x = pos[i][j - 1];
      for (iter = 0; iter < 63; iter++) {
        if (x + 1 < n) {
          x = pos[x + 1][j - 1];
        } else {
          x = n;
        }
      }
      pos[i][j] = x;
    }
  }
  int q;
  cin >> q;
  int l, r, ans;
  while (q--) {
    cin >> l >> r;
    --l; --r;
    ans = 0;
    for (i = L - 1; i >= 0; i--) {
      while (l < n && pos[l][i] <= r) {
        ans += pw[i];
        l = pos[l][i] + 1;
      }
    }
    while (l < n && R[l] <= r) {
      ans++;
      l = R[l] + 1;
    }
    cout << ans << '\n';
  }
  return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 115 ms 3868 KB Output is correct
8 Correct 80 ms 4508 KB Output is correct
9 Correct 117 ms 2976 KB Output is correct
10 Correct 134 ms 3880 KB Output is correct
11 Correct 83 ms 3752 KB Output is correct
12 Correct 118 ms 2868 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 115 ms 3868 KB Output is correct
8 Correct 80 ms 4508 KB Output is correct
9 Correct 117 ms 2976 KB Output is correct
10 Correct 134 ms 3880 KB Output is correct
11 Correct 83 ms 3752 KB Output is correct
12 Correct 118 ms 2868 KB Output is correct
13 Correct 573 ms 14972 KB Output is correct
14 Correct 444 ms 17268 KB Output is correct
15 Correct 660 ms 9448 KB Output is correct
16 Correct 706 ms 17428 KB Output is correct
17 Correct 481 ms 14324 KB Output is correct
18 Correct 597 ms 9288 KB Output is correct