Submission #1137132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137132		Pwo	Sum Zero (RMI20_sumzero)	C++20	61 / 100	654 ms	77596 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, q, a[400005], p[400005];
unordered_map<int, int> mp;
int up[400005][20];

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n; n++;
	for (int i = 2; i <= n; i++) cin >> a[i];
	
	int sum = 0; p[1] = 0; mp[0] = 1;
	for (int i = 2; i <= n; i++) {
		sum += a[i];
		p[i] = p[i - 1];
		if (mp.find(sum) != mp.end())
			p[i] = max(p[i], mp[sum]);
		mp[sum] = i;
		up[i][0] = p[i];
		for (int j = 1; j <= 18; j++)
			up[i][j] = up[up[i][j - 1]][j - 1];
	}
	
	cin >> q;
	while (q--) {
		int l, r; cin >> l >> r; l++, r++;
		int ans = 0;
		for (int i = 18; i >= 0; i--) {
			if (up[r][i] + 1 >= l)
				r = up[r][i], ans |= (1 << i);
		}
		cout << ans << '\n';
	}
}

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 0 / 39