oj.uz

Submission #857712

# Submission time Handle Problem Language Result Execution time Memory
857712 2023-10-06T16:15:28 Z alexdumitru Sum Zero (RMI20_sumzero) C++14
100 / 100
 220 ms 13440 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int kN = 4e5;
int nxt[1 + kN], jump[1 + kN + 1 + 1];
long long 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 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 3 ms 10720 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 4 ms 10584 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 3 ms 10720 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 4 ms 10584 KB Output is correct
7 Correct 46 ms 11092 KB Output is correct
8 Correct 46 ms 11092 KB Output is correct
9 Correct 50 ms 11348 KB Output is correct
10 Correct 47 ms 11132 KB Output is correct
11 Correct 47 ms 11144 KB Output is correct
12 Correct 50 ms 11344 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10588 KB Output is correct
2 Correct 3 ms 10588 KB Output is correct
3 Correct 3 ms 10720 KB Output is correct
4 Correct 4 ms 10588 KB Output is correct
5 Correct 3 ms 10588 KB Output is correct
6 Correct 4 ms 10584 KB Output is correct
7 Correct 46 ms 11092 KB Output is correct
8 Correct 46 ms 11092 KB Output is correct
9 Correct 50 ms 11348 KB Output is correct
10 Correct 47 ms 11132 KB Output is correct
11 Correct 47 ms 11144 KB Output is correct
12 Correct 50 ms 11344 KB Output is correct
13 Correct 206 ms 13396 KB Output is correct
14 Correct 187 ms 13120 KB Output is correct
15 Correct 214 ms 13392 KB Output is correct
16 Correct 202 ms 13140 KB Output is correct
17 Correct 186 ms 13140 KB Output is correct
18 Correct 220 ms 13440 KB Output is correct