Submission #947773

#	Time	Username	Problem	Language	Result	Execution time	Memory
947773		NK_	Sum Zero (RMI20_sumzero)	C++17	100 / 100	365 ms	15540 KiB

sumzero

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define sz(x) int(x.size())
#define pb push_back
 
using ll = long long;
template<class T> using V = vector<T>;
using vl = V<ll>;
 
const int nax = 4e5+2;
const int K = 16;
const int LG = 5;
 
int nxt[nax][LG], ord[nax], N, i, j, t, _, l, r, Q, ans;
ll A[nax];
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	for(i = 0; i < nax; i++) for(j = 0; j < LG; j++) nxt[i][j] = nax - 1;
 
	cin >> N;

	A[0] = ord[0] = 0;	
	for(i = 1; i <= N; i++) {
		cin >> A[i]; 
		A[i] += A[i - 1];
		ord[i] = i;
	}
 
	sort(ord, ord + N + 1, [&](const int &x, const int &y) {
		if (A[x] == A[y]) return x < y;
		return A[x] < A[y];
	});

	for(i = 0; i <= N; i++) {
		if (i + 1 <= N && A[ord[i]] == A[ord[i + 1]]) {
			nxt[ord[i]][0] = ord[i + 1];
			// cout << ord[i] << " --> " << ord[i + 1] << endl;
		} else nxt[ord[i]][0] = nax - 1;
	}
 
 	for(i = N - 1; i >= 0; i--) {
		if (i + 1 < N) nxt[i][0] = min(nxt[i][0], nxt[i + 1][0]);
 
		for(t = 1; t < LG; t++) {
			// nxt[i][t] = nxt[nxt[nxt[...nxt[i][t-1]][t-1]][t-1]..]
			nxt[i][t] = nxt[i][t-1];
			for(_ = 0; _ < K - 1; _++) nxt[i][t] = nxt[nxt[i][t]][t-1];
		}
	}
 
 
	cin >> Q;
	while(Q--) {
		cin >> l >> r; --l;
 
		ans = 0;
		for(t = LG - 1; t >= 0; t--) {
			while(nxt[l][t] <= r) {
				ans += (1 << (4 * t));
				l = nxt[l][t];
			}
		}
 
		cout << ans << nl;
	}
 
	exit(0-0);
}

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