Submission #1297599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297599		aeg	Sum Zero (RMI20_sumzero)	C++20	61 / 100	239 ms	27464 KiB

sumzero

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

int dfs(int s, vector<vector<int>> const&child, vector<int>& heavy) {
	int sz = 1;
	int chmax = 0;
	for(auto &ch : child[s]) {
		int chsz = dfs(ch, child, heavy);
		sz += chsz;
		if(chsz > chmax) {
			heavy[s] = ch;
			chmax = chsz;
		}
	}
	return sz;
}

void decompose(int s, int h, vector<vector<int>> const&child, vector<int>const& heavy, vector<int>& head, vector<int>& pos, int& curpos) {
	head[s] = h, pos[s] = curpos++;
	if(heavy[s] != -1)
		decompose(heavy[s], h, child, heavy, head, pos, curpos);
	for(auto &ch:child[s]) if(ch != heavy[s]) {
		decompose(ch, ch, child, heavy, head, pos, curpos);
	}
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> next(n + 1);
	vector<int> a(n + 1);
	vector<int> pref(n + 1);
	next[n] = INT_MAX;
	{
		pref[0] = 0;

		map<int, int> mp;

		for(int i= 0; i < n; i ++) cin >> a[i];
		for(int i = 0; i < n; i ++) pref[i + 1] = pref[i] + a[i];
		for(int i = n - 1; i >= 0; i --) {
			mp[pref[i + 1]] = i;
			if(mp.count(pref[i])) next[i] = min(mp[pref[i]], next[i + 1]);
			else next[i] = next[i + 1];
		}

		mp.clear();
	} // garbage collection
	fill(a.begin(), a.end(), 0);
	fill(pref.begin(), pref.end(), -1);
	{
		vector<vector<int>> child;
		while(child.size() < n) {
			child.push_back(vector<int>());
			child.back().shrink_to_fit();
		}
		for(int i = 0; i < n; i ++) if(next[i] < n && next[i] >= 0) child[next[i] + 1].emplace_back(i);
		next.clear();
		next.shrink_to_fit();
		vector<int> heavy(n + 1, -1);
		{
			int cp = 0;
			for(int i = n; i >= 0; i --) {
				if(pref[i] != -1) continue;
				dfs(i, child, heavy);
				decompose(i, i, child, heavy, a, pref, cp);
			}
		}
		heavy.clear();
		heavy.shrink_to_fit();
		next.assign(n + 1, -1);
		for(int i = 0; i < n; i ++) for(auto &x:child[i]) next[x] = i - 1;
		child.clear();
		child.shrink_to_fit();
	} // garbage collection
	
	vector<int> revpos(n + 1);
	for(int i = 0; i <= n; i ++) revpos[pref[i]] = i;

	for(int i = 0; i <= n; i ++) {
		if(next[i] == -1 || next[i] == INT_MAX) next[i] = -1;
		else next[i]++;
	}

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

		int curl = l;
		int curd = 0;
		while(true) {
			if(a[curl] <= r) {
				if(next[a[curl]] < 0) {
					curd += pref[curl] - pref[a[curl]];
					curl = a[curl];
					break;
				}
				else {
					curd += pref[curl] - pref[a[curl]]+ 1;
					curl = next[a[curl]];
				}
			}
			else break;
		}
		if(a[curl] == curl && next[curl] < 0) {
			if(curl > r) cout << "0\n";
			else cout << curd << '\n';
			continue;
		}
		int ll = pref[a[curl]], rr = pref[curl];
		int ans = INT_MAX;
		while(ll <= rr) {
			int m = (ll + rr) >> 1;
			if(revpos[m] <= r) {
				rr = m - 1;
				ans = min(ans, m);
			}
			else {
				ll = m + 1;
			}
		}
		if(ans == INT_MAX) cout  << max(0, curd - 1) << '\n';
		else cout << curd + pref[curl] - ans << '\n';
	}
}

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