oj.uz

Submission #875110

# Submission time Handle Problem Language Result Execution time Memory
875110 2023-11-18T17:03:41 Z MinaRagy06 Sum Zero (RMI20_sumzero) C++14
100 / 100
 773 ms 13652 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 400'005, LG = 3, B = 7;
int nxt[LG][N], a[N], lst[N];
ll prfx = 0, comp[N];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		prfx += a[i];
		comp[i] = prfx;
	}
	sort(comp, comp + n + 1);
	memset(lst, -1, sizeof lst);
	int mn = n + 1;
	for (int i = n; i >= 0; i--) {
		int idx = lower_bound(comp, comp + n + 1, prfx) - comp;
		if (lst[idx] != -1) {
			mn = min(mn, lst[idx]);
		}
		lst[idx] = i;
		nxt[0][i] = mn;
		prfx -= a[i];
	}
	nxt[0][n + 1] = n + 1;
	for (int j = 1; j < LG; j++) {
		for (int i = 0; i <= n + 1; i++) {
			nxt[j][i] = nxt[j - 1][i];
			for (int k = 1; k < (1 << B); k++) {
				nxt[j][i] = nxt[j - 1][nxt[j][i]];
			}
		}
	}
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		l--;
		int ans = 0;
		for (int j = LG - 1; j >= 0; j--) {
			while (nxt[j][l] <= r) {
				ans += 1 << (B * j);
				l = nxt[j][l];
			}
		}
		cout << ans << '\n';
	}
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7768 KB Output is correct
2 Correct 5 ms 7772 KB Output is correct
3 Correct 6 ms 7772 KB Output is correct
4 Correct 5 ms 7768 KB Output is correct
5 Correct 5 ms 7772 KB Output is correct
6 Correct 7 ms 7816 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7768 KB Output is correct
2 Correct 5 ms 7772 KB Output is correct
3 Correct 6 ms 7772 KB Output is correct
4 Correct 5 ms 7768 KB Output is correct
5 Correct 5 ms 7772 KB Output is correct
6 Correct 7 ms 7816 KB Output is correct
7 Correct 112 ms 10260 KB Output is correct
8 Correct 94 ms 10440 KB Output is correct
9 Correct 132 ms 10240 KB Output is correct
10 Correct 121 ms 10320 KB Output is correct
11 Correct 91 ms 10320 KB Output is correct
12 Correct 118 ms 10324 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7768 KB Output is correct
2 Correct 5 ms 7772 KB Output is correct
3 Correct 6 ms 7772 KB Output is correct
4 Correct 5 ms 7768 KB Output is correct
5 Correct 5 ms 7772 KB Output is correct
6 Correct 7 ms 7816 KB Output is correct
7 Correct 112 ms 10260 KB Output is correct
8 Correct 94 ms 10440 KB Output is correct
9 Correct 132 ms 10240 KB Output is correct
10 Correct 121 ms 10320 KB Output is correct
11 Correct 91 ms 10320 KB Output is correct
12 Correct 118 ms 10324 KB Output is correct
13 Correct 616 ms 13388 KB Output is correct
14 Correct 443 ms 13064 KB Output is correct
15 Correct 773 ms 13652 KB Output is correct
16 Correct 641 ms 13216 KB Output is correct
17 Correct 437 ms 13220 KB Output is correct
18 Correct 693 ms 13396 KB Output is correct