oj.uz

Submission #970914

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

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

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

void build_rmq() {
  int cur, ti;
  for (int j = 1; j <= 5; ++j)
    for (int i = 1; i + (1 << (j * 2)) - 1 <= n; ++i) {
    	cur = i;
      for (int ti = 1; ti <= 16; ++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 = 4; i >= 0; --i)
    while (ku[l][i] != 0 && ku[l][i] <= r) {
      ans += 1 << (i * 4);
      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 600 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 76 ms 7784 KB Output is correct
8 Correct 72 ms 8020 KB Output is correct
9 Correct 80 ms 5640 KB Output is correct
10 Correct 77 ms 7644 KB Output is correct
11 Correct 65 ms 7248 KB Output is correct
12 Correct 83 ms 5836 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 76 ms 7784 KB Output is correct
8 Correct 72 ms 8020 KB Output is correct
9 Correct 80 ms 5640 KB Output is correct
10 Correct 77 ms 7644 KB Output is correct
11 Correct 65 ms 7248 KB Output is correct
12 Correct 83 ms 5836 KB Output is correct
13 Runtime error 383 ms 22100 KB Memory limit exceeded
14 Halted 0 ms 0 KB -