oj.uz

Submission #970806

# Submission time Handle Problem Language Result Execution time Memory
970806 2024-04-27T10:03:47 Z lmaobruh Sum Zero (RMI20_sumzero) C++14
61 / 100
 328 ms 29792 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

void build_rmq() {
  for (int i = 1; i <= n; ++i) ku[i][0] = nxt[i];
  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) nxt[i] = -1;
  for (int i = 1; i <= n; ++i) {
    cin >> x;
    sum += x;
    if (mp.count(sum)) nxt[mp[sum] + 1] = i;
    mp[sum] = i;
  }
  mp.clear();
  int pre = -1;
  for (int i = n; i >= 1; --i) {
    if (nxt[i] != -1) pre = (pre == -1 ? nxt[i] : min(pre, nxt[i]));
    else nxt[i] = 0;
    nxt[i] = (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:12:12: warning: unused variable 'ti' [-Wunused-variable]
   12 |   int cur, ti;
      |            ^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 5 ms 4936 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 5 ms 4936 KB Output is correct
7 Correct 64 ms 9584 KB Output is correct
8 Correct 59 ms 10068 KB Output is correct
9 Correct 68 ms 7784 KB Output is correct
10 Correct 60 ms 9552 KB Output is correct
11 Correct 67 ms 9448 KB Output is correct
12 Correct 76 ms 8012 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4700 KB Output is correct
2 Correct 3 ms 4700 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4700 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 5 ms 4936 KB Output is correct
7 Correct 64 ms 9584 KB Output is correct
8 Correct 59 ms 10068 KB Output is correct
9 Correct 68 ms 7784 KB Output is correct
10 Correct 60 ms 9552 KB Output is correct
11 Correct 67 ms 9448 KB Output is correct
12 Correct 76 ms 8012 KB Output is correct
13 Runtime error 328 ms 29792 KB Memory limit exceeded
14 Halted 0 ms 0 KB -