Submission #1272633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272633		algoproclub	Sum Zero (RMI20_sumzero)	C++20	61 / 100	1012 ms	79248 KiB

sumzero

// UUID: 18f9ee18-a136-49ed-bf86-df7923a0e383
#include <bits/stdc++.h>
using namespace std;

int main() {

	int n, K = 20;
	cin >> n;
	vector<long long> v(n+1), pr(n+1);
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		pr[i]=pr[i-1]+v[i];
	}
	vector<int> par(n+1, -1),  last(n+1);
	last[0]=-1;
	map<long long, int> mep;
	map<long long, bool> mep2;
	mep2[0]=1;
	for (int i = 1; i <= n; i++) {
		if (mep2[pr[i]]) {
			par[i]=mep[pr[i]];
		}
		mep2[pr[i]]=1;
		mep[pr[i]]=i;
		last[i]=max(last[i-1], par[i]);
		//cerr << par[i] << ' ';
	}
	//cerr<<'\n';
	vector<vector<int>> up(n+1, vector<int>(K+1));
	for (int i = 0; i <= K; i++)up[0][i]=-1;
	for (int i = 1; i <= n; i++) {
		up[i][0] = last[i];
		for (int j = 1; j <= K; j++) {
			if (up[i][j-1]==-1)up[i][j]=-1;
			else up[i][j] = up[up[i][j-1]][j-1];
		}
	}
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		int ans = 0, ind = r;
		for (int i = K; i >= 0; i--) {
			if (up[ind][i]>=l-1) {
				ans += 1<<i;
				ind = up[ind][i];
			}
		}
		cout << ans << endl;
		//for(int i = 0; i <= K; i++)cerr<<up[r][i]<<' ';
		//cerr<<'\n';
	}
}

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