제출 #874909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874909		TAhmed33	Sum Zero (RMI20_sumzero)	C++98	22 / 100	68 ms	25212 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[5][MAXN], n;
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) c[4][pos] = 1 + c[4][par];
	c[1][++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 (c[1][mid] <= x) {
				r = mid - 1; anss = c[1][mid];
			} else {
				l = mid + 1;
			}
		}
		int z = -c[4][anss] + c[4][pos];
		if (c[2][anss] <= x) z++;
		c[3][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(c[4], -1, sizeof(c[4]));
	for (int i = 0; i < MAXN; i++) edges[i] = {inf, inf};
	for (int i = 1; i <= n; i++) {
		cin >> c[0][i];
		c[0][i] += c[0][i - 1]; c[1][++sze] = c[0][i];
	}
	sort(c[1], c[1] + MAXN); 
	for (int i = 0; i <= n; i++) c[0][i] = lower_bound(c[1], c[1] + MAXN, c[0][i]) - c[1];
	sze = 0;
	for (int i = n; i >= 0; i--) {
		c[2][i] = c[4][c[0][i]] != -1 ? c[4][c[0][i]] : inf;
		c[4][c[0][i]] = i;
		swap(edges[c[0][i]].first, edges[c[0][i]].second);
		edges[c[0][i]].second = i;
		if (edges[c[0][i]].first < mnn) {
			mnn = edges[c[0][i]].first; pos = edges[c[0][i]].second;
		}
		c[3][i] = pos;
	} 
	for (int i = n; i >= 0; i--) {
		int u;
		if (c[2][i] == inf) u = inf;
		else u = c[3][c[2][i]];
		if (u != inf) edges[++sze2] = {u, i};
		else c[4][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 = c[3][l - 1];
		if (cur == inf || c[2][cur] > r) {
			cur = inf;
		}
		qs[++sze3] = {cur, r, i};
	}
	sort(qs + 1, qs + sze3 + 1);
	for (int i = 0; i <= n; i++) {
		if (c[4][i] == 1) dfs(i, -1);
	}
	while (sze3 && qs[sze3][0] == inf) {
		c[3][qs[sze3][2]] = 0;
		sze3--;
	}
	for (int i = 1; i <= q; i++) cout << c[3][i] << '\n';
}
	

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