Submission #874834

#	Time	Username	Problem	Language	Result	Execution time	Memory
874834		TAhmed33	Sum Zero (RMI20_sumzero)	C++98	61 / 100	417 ms	30684 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
const int MAXN = 4e5 + 1;
const int inf = 1e9;
typedef long long ll;
ll c[MAXN], comp[MAXN], n;
int lst[MAXN], pp[MAXN], dd[MAXN], ans[MAXN];
pair <int, int> edges[MAXN];
int mnn = inf;
int pos = inf;
array <int, 3> qs[MAXN];
int sze = 0, sze2 = 0, sze3 = 0;
void dfs (int pos, int par) {
	if (par != -1) dd[pos] = 1 + dd[par];
	comp[++sze] = pos;
	array <int, 3> j = {pos, 0, 0};
	auto t = lower_bound(qs + 1, qs + sze3 + 1, j) - qs;
	while (t <= sze3 && qs[t][0] == pos) {
		int x = qs[t][1], y = qs[t][2];
		int l = 1, r = sze, anss = -1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (comp[mid] <= x) {
				r = mid - 1; anss = comp[mid];
			} else {
				l = mid + 1;
			}
		}
		int z = -dd[anss] + dd[pos];
		if (lst[anss] <= x) z++;
		ans[y] = z; t++;
	}
	pair <int, int> j2 = {pos, 0};
	t = lower_bound(edges + 1, edges + sze2 + 1, j2) - edges;
	while (t <= sze2 && edges[t].first == pos) {
		dfs(edges[t].second, pos); t++;
	}
	sze--;
}
signed main () {
	//ios::sync_with_stdio(0); cin.tie(0);
	cin >> n; memset(dd, -1, sizeof(dd));
	for (int i = 0; i < MAXN; i++) edges[i] = {inf, inf};
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
		c[i] += c[i - 1]; comp[++sze] = c[i];
	}
	sort(comp, comp + MAXN); 
	for (int i = 0; i <= n; i++) c[i] = lower_bound(comp, comp + MAXN, c[i]) - comp;
	sze = 0;
	for (int i = n; i >= 0; i--) {
		lst[i] = dd[c[i]] != -1 ? dd[c[i]] : inf;
		dd[c[i]] = i;
		swap(edges[c[i]].first, edges[c[i]].second);
		edges[c[i]].second = i;
		if (edges[c[i]].first < mnn) {
			mnn = edges[c[i]].first; pos = edges[c[i]].second;
		}
		pp[i] = pos;
	} 
	for (int i = n; i >= 0; i--) {
		int u;
		if (lst[i] == inf) u = inf;
		else u = pp[lst[i]];
		if (u != inf) edges[++sze2] = {u, i};
		else dd[i] = 1;
	}
	sort(edges + 1, edges + sze2 + 1);
	int q;
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		int cur = pp[l - 1];
		if (cur == inf || lst[cur] > r) {
			ans[i] = 0;
			continue;
		}
		qs[++sze3] = {cur, r, i};
	}
	sort(qs + 1, qs + sze3 + 1);
	for (int i = 0; i <= n; i++) {
		if (dd[i] == 1) dfs(i, -1);
	}
	for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
	

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