oj.uz

Submission #857711

# Submission time Handle Problem Language Result Execution time Memory
857711 2023-10-06T16:13:54 Z alexdumitru Sum Zero (RMI20_sumzero) C++14
100 / 100
 235 ms 13648 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int kN = 4e5;
int nxt[1 + kN], jump[1 + kN + 1 + 1];
int64_t sum[1 + kN];

int L[1 + kN], R[1 + kN], ANS[1 + kN];

void testCase() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> sum[i];
    sum[i] += sum[i - 1];
  }
  multiset<int64_t> sums{0};
  int r = 0;
  for (int l = 1; l <= n; ++l) {
    while (r <= n) {
      if (sums.count(sum[r]) >= 2) {
        break;
      }
      r += 1;
      sums.emplace(sum[r]);
    }
    nxt[l] = r + 1;
    sums.erase(sums.find(sum[l - 1]));
  }
  int Q;
  cin >> Q;
  for (int i = 1; i <= Q; ++i) {
    cin >> L[i] >> R[i];
    ANS[i] = 0;
  }
  jump[n + 1] = jump[n + 2] = n + 2;
  for (int j = log2(n); j >= 0; --j) {
    for (int i = 1; i <= n; ++i) {
      jump[i] = nxt[i];
    }
    for (int rep = 1; rep <= j; ++rep) {
      for (int i = 1; i <= n; ++i) {
        jump[i] = jump[jump[i]];
      }
    }
    for (int i = 1; i <= Q; ++i) {
      if (jump[L[i]] <= R[i] + 1) {
        ANS[i] += (1 << j);
        L[i] = jump[L[i]];
      }
    }
  }
  for (int i = 1; i <= Q; ++i) {
    cout << ANS[i] << '\n';
  }
}
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 1; tc <= tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 3 ms 10636 KB Output is correct
3 Correct 4 ms 10588 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Correct 4 ms 10588 KB Output is correct
7 Correct 49 ms 11340 KB Output is correct
8 Correct 46 ms 11092 KB Output is correct
9 Correct 52 ms 11224 KB Output is correct
10 Correct 48 ms 11092 KB Output is correct
11 Correct 46 ms 11092 KB Output is correct
12 Correct 53 ms 11132 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Correct 3 ms 10636 KB Output is correct
3 Correct 4 ms 10588 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 4 ms 10588 KB Output is correct
6 Correct 4 ms 10588 KB Output is correct
7 Correct 49 ms 11340 KB Output is correct
8 Correct 46 ms 11092 KB Output is correct
9 Correct 52 ms 11224 KB Output is correct
10 Correct 48 ms 11092 KB Output is correct
11 Correct 46 ms 11092 KB Output is correct
12 Correct 53 ms 11132 KB Output is correct
13 Correct 219 ms 13364 KB Output is correct
14 Correct 197 ms 13136 KB Output is correct
15 Correct 235 ms 13648 KB Output is correct
16 Correct 217 ms 13188 KB Output is correct
17 Correct 196 ms 13084 KB Output is correct
18 Correct 227 ms 13444 KB Output is correct