Submission #1257028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257028		nguyn	Sum Zero (RMI20_sumzero)	C++20	61 / 100	471 ms	81468 KiB

sumzero

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

#define int long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 5e5 + 5;

int nxt[N][20]; 
int n, q; 
int a[N]; 
int p[N]; 
map<int, int> mp;

signed main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		p[i] = p[i - 1] + a[i];
	}
	cin >> q; 
	nxt[n + 1][0] = n + 1;
	nxt[n + 2][0] = n + 1;
	for (int i = n; i >= 1; i--) {
		mp[p[i]] = i;  
		if (mp.count(p[i - 1])) nxt[i][0] = min(nxt[i + 1][0], mp[p[i - 1]]);  
		else nxt[i][0] = nxt[i + 1][0];
//		cout << nxt[i][0] << ' ';
	}
//	cout << '\n';
//	cout << '\n';
	for (int i = 1; i < 20; i++) {
		for (int j = 1; j <= n + 2; j++) {
			nxt[j][i] = nxt[nxt[j][i - 1] + 1][i - 1]; 
		}
	}
	while(q--) {
		int l, r;
		cin >> l >> r;
		assert(r <= n);
		int res = 0; 
		for (int i = 19; i >= 0; i--) {
//			cout << l << ' ' << i << ' ' << nxt[l][i] << endl;
			if (nxt[l][i] <= r) {
				l = nxt[l][i] + 1; 
				res += (1 << i); 
			}
		}
		cout << res << '\n'; 
	}
	
}

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