oj.uz

Submission #682870

# Submission time Handle Problem Language Result Execution time Memory
682870 2023-01-17T06:24:48 Z MilosMilutinovic Sum Zero (RMI20_sumzero) C++14
100 / 100
 706 ms 17516 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;
  vector<int> R(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 5 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 5 ms 496 KB Output is correct
6 Correct 6 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 5 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 5 ms 496 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 136 ms 3876 KB Output is correct
8 Correct 82 ms 4444 KB Output is correct
9 Correct 130 ms 2940 KB Output is correct
10 Correct 127 ms 3888 KB Output is correct
11 Correct 83 ms 3764 KB Output is correct
12 Correct 120 ms 2848 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 5 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 5 ms 496 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 136 ms 3876 KB Output is correct
8 Correct 82 ms 4444 KB Output is correct
9 Correct 130 ms 2940 KB Output is correct
10 Correct 127 ms 3888 KB Output is correct
11 Correct 83 ms 3764 KB Output is correct
12 Correct 120 ms 2848 KB Output is correct
13 Correct 694 ms 14944 KB Output is correct
14 Correct 492 ms 17348 KB Output is correct
15 Correct 634 ms 9364 KB Output is correct
16 Correct 686 ms 17516 KB Output is correct
17 Correct 512 ms 14452 KB Output is correct
18 Correct 706 ms 16340 KB Output is correct