oj.uz

Submission #970912

# Submission time Handle Problem Language Result Execution time Memory
970912 2024-04-27T13:55:26 Z lmaobruh Sum Zero (RMI20_sumzero) C++14
61 / 100
 382 ms 34680 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 4e5 + 5;

int n, q, ku[N][10];
map<ll, int> mp;

void build_rmq() {
  int cur, ti;
  for (int j = 1; j <= 9; ++j)
    for (int i = 1; i + (1 << (j * 2)) - 1 <= n; ++i) {
    	cur = i;
      for (int ti = 1; ti <= 4; ++ti) {
        cur = ku[cur][j - 1];
        if (cur == 0) break;
        else cur++;
      }
      if (cur == 0) {
        ku[i][j] = 0;
        continue;
      }
      ku[i][j] = cur - 1;
    }
}

void build() {
  cin >> n;
  ll sum = 0, x;
  mp[0] = 0;
  for (int i = 1; i <= n; ++i) ku[i][0] = -1;
  for (int i = 1; i <= n; ++i) {
    cin >> x;
    sum += x;
    if (mp.count(sum)) ku[mp[sum] + 1][0] = i;
    mp[sum] = i;
  }
  mp.clear();
  int pre = -1;
  for (int i = n; i >= 1; --i) {
    if (ku[i][0] != -1) pre = (pre == -1 ? ku[i][0] : min(pre, ku[i][0]));
    else ku[i][0] = 0;
    ku[i][0] = (pre != -1 ? pre : 0);
  }
  build_rmq();
}

int ans;
int que(int l, int r) {
	ans = 0;
  for (int i = 9; i >= 0; --i)
    while (ku[l][i] != 0 && ku[l][i] <= r) {
      ans += 1 << (i * 2);
      l = ku[l][i] + 1;
    }
  return ans;
}

void ouput() {
  cin >> q;
  while (q--) {
    static int l, r; cin >> l >> r;
    cout << que(l, r) << '\n';
  }
}

void solve() {
  build();
  ouput();
}

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  solve();
  return 0;
}

Compilation message

sumzero.cpp: In function 'void build_rmq()':
sumzero.cpp:11:12: warning: unused variable 'ti' [-Wunused-variable]
   11 |   int cur, ti;
      |            ^~

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 3 ms 2908 KB Output is correct
3 Correct 4 ms 2780 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 67 ms 9056 KB Output is correct
8 Correct 62 ms 9808 KB Output is correct
9 Correct 66 ms 7252 KB Output is correct
10 Correct 61 ms 9056 KB Output is correct
11 Correct 56 ms 9040 KB Output is correct
12 Correct 73 ms 7292 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 3 ms 2908 KB Output is correct
3 Correct 4 ms 2780 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 3 ms 2652 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 67 ms 9056 KB Output is correct
8 Correct 62 ms 9808 KB Output is correct
9 Correct 66 ms 7252 KB Output is correct
10 Correct 61 ms 9056 KB Output is correct
11 Correct 56 ms 9040 KB Output is correct
12 Correct 73 ms 7292 KB Output is correct
13 Runtime error 382 ms 34680 KB Memory limit exceeded
14 Halted 0 ms 0 KB -