oj.uz

Submission #950355

# Submission time Handle Problem Language Result Execution time Memory
950355 2024-03-20T08:47:33 Z TrieTr Sum Zero (RMI20_sumzero) C++14
100 / 100
 221 ms 17504 KB 
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N = 4e5 + 5;

int n, q, res;
int arr[N];
unordered_map<ll, int> pos;
int nxt[N];
int h[N], jump[N];
int i;

void make_leaf(int& id, int& p) {
	h[id] = h[p] + 1;
	if(h[jump[p]] - h[p] == h[jump[jump[p]]] - h[jump[p]]) jump[id] = jump[jump[p]];
	else jump[id] = p;
}
int main() {
    fastio;
    cin >> n;
    for(i = 1; i <= n; i++) cin >> arr[i];
    ll sum = 0;
    nxt[n + 1] = n + 1;
    pos[0] = n + 1;
    for(i = n; i > 0; i--) {
    	sum += arr[i];
    	nxt[i] = pos[sum] - 1;
    	nxt[i] = (nxt[i] == -1 ? nxt[i + 1] : min(nxt[i], nxt[i + 1]));
    	pos[sum] = i;
	}
	for(i = n; i > 0; i--) {
		int u = nxt[i];
		if(h[u] > 0 || u > n) continue;
		int p = nxt[u + 1];
		make_leaf(u, p);
	}
	cin >> q;
	while(q--) {
		int l, r; cin >> l >> r;
		l = nxt[l];
        if(l > r) {cout << "0\n"; continue;}
        res = 0;
		while(l <= r && l != 0) {
			if(jump[l] <= r && jump[l] != 0) {
				res += h[l] - h[jump[l]];
				l = jump[l];
			}
			else {
				res++;
				l = nxt[l + 1];
			}
		}
		cout << res << '\n';
	}
}

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2720 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 3 ms 2516 KB Output is correct
7 Correct 44 ms 5572 KB Output is correct
8 Correct 40 ms 6252 KB Output is correct
9 Correct 46 ms 4632 KB Output is correct
10 Correct 42 ms 5552 KB Output is correct
11 Correct 40 ms 5552 KB Output is correct
12 Correct 46 ms 4688 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2720 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 3 ms 2516 KB Output is correct
7 Correct 44 ms 5572 KB Output is correct
8 Correct 40 ms 6252 KB Output is correct
9 Correct 46 ms 4632 KB Output is correct
10 Correct 42 ms 5552 KB Output is correct
11 Correct 40 ms 5552 KB Output is correct
12 Correct 46 ms 4688 KB Output is correct
13 Correct 200 ms 15040 KB Output is correct
14 Correct 190 ms 17292 KB Output is correct
15 Correct 221 ms 9584 KB Output is correct
16 Correct 209 ms 17504 KB Output is correct
17 Correct 183 ms 14428 KB Output is correct
18 Correct 214 ms 16268 KB Output is correct