oj.uz

Submission #927417

# Submission time Handle Problem Language Result Execution time Memory
927417 2024-02-14T20:22:37 Z TAhmed33 Sum Zero (RMI20_sumzero) C++
100 / 100
 997 ms 18516 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 25;
typedef long long ll;
int p[MAXN], par[MAXN];
int n; pair <ll, int> d2[MAXN];
const int SZE = 630;
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n; 
	for (int i = 0; i <= n + 1; i++) p[i] = n + 1;
	ll cur = 0; d2[0] = {0, 0};
	for (int i = 1; i <= n; i++) {
		ll x; cin >> x; cur += x; d2[i] = {cur, i};
	}
	sort(d2, d2 + n + 1);
	for (int i = 0; i < n; i++) {
		if (d2[i].first == d2[i + 1].first) {
			p[d2[i].second] = d2[i + 1].second;
		}
	}
	for (int i = n; i >= 0; i--) {
		p[i] = min(p[i], p[i + 1]);
		par[i] = i;
		for (int j = 0; j < SZE; j++) {
			par[i] = p[par[i]];
		}
	}
	int q; cin >> q;
	while (q--) {
		int l, r; cin >> l >> r;
		l--;
		int ans = 0;
		while (par[l] <= r) {
			l = par[l]; ans += SZE;
		}
		while (p[l] <= r) {
			l = p[l]; ans++;
		}
		cout << ans << '\n';
	}
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4444 KB Output is correct
2 Correct 8 ms 4444 KB Output is correct
3 Correct 9 ms 4660 KB Output is correct
4 Correct 10 ms 4444 KB Output is correct
5 Correct 8 ms 4444 KB Output is correct
6 Correct 9 ms 4444 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4444 KB Output is correct
2 Correct 8 ms 4444 KB Output is correct
3 Correct 9 ms 4660 KB Output is correct
4 Correct 10 ms 4444 KB Output is correct
5 Correct 8 ms 4444 KB Output is correct
6 Correct 9 ms 4444 KB Output is correct
7 Correct 194 ms 6996 KB Output is correct
8 Correct 179 ms 6996 KB Output is correct
9 Correct 212 ms 7052 KB Output is correct
10 Correct 198 ms 7260 KB Output is correct
11 Correct 181 ms 7028 KB Output is correct
12 Correct 214 ms 7504 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4444 KB Output is correct
2 Correct 8 ms 4444 KB Output is correct
3 Correct 9 ms 4660 KB Output is correct
4 Correct 10 ms 4444 KB Output is correct
5 Correct 8 ms 4444 KB Output is correct
6 Correct 9 ms 4444 KB Output is correct
7 Correct 194 ms 6996 KB Output is correct
8 Correct 179 ms 6996 KB Output is correct
9 Correct 212 ms 7052 KB Output is correct
10 Correct 198 ms 7260 KB Output is correct
11 Correct 181 ms 7028 KB Output is correct
12 Correct 214 ms 7504 KB Output is correct
13 Correct 910 ms 11616 KB Output is correct
14 Correct 863 ms 11364 KB Output is correct
15 Correct 979 ms 12156 KB Output is correct
16 Correct 886 ms 12000 KB Output is correct
17 Correct 850 ms 11592 KB Output is correct
18 Correct 997 ms 18516 KB Output is correct