Submission #947749

#	Time	Username	Problem	Language	Result	Execution time	Memory
947749		NK_	Sum Zero (RMI20_sumzero)	C++17	61 / 100	404 ms	29432 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+5;
const int K = 16;
const int LG = 5;

int nxt[nax][LG];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	for(int i = 0; i < nax; i++) for(int j = 0; j < LG; j++) nxt[i][j] = nax - 1;

	int N; cin >> N;
	vl A(N); for(auto& x : A) cin >> x;

	vl P = {0}; for(auto& x : A) P.pb(P.back() + x);

	unordered_map<ll, int> lst; lst[P.back()] = N;
	for(int i = N - 1; i >= 0; i--) {
		if (lst.find(P[i]) == lst.end()) nxt[i][0] = nax - 1;
		else nxt[i][0] = lst[P[i]];

		if (i + 1 < N) nxt[i][0] = min(nxt[i][0], nxt[i + 1][0]);
		lst[P[i]] = i;

		for(int 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(int _ = 0; _ < K - 1; _++) nxt[i][t] = nxt[nxt[i][t]][t-1];
		}
	}


	int Q; cin >> Q;
	while(Q--) {
		int l, r; cin >> l >> r; --l;

		int ans = 0;
		for(int 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: 0 / 39