제출 #874812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
874812		TAhmed33	Sum Zero (RMI20_sumzero)	C++98	22 / 100	125 ms	21948 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
const int inf2 = 17;
#define ll long long 
const ll inf = 1e9;
ll c[MAXN], n;
ll lst[MAXN];
ll pp[MAXN];
ll nxt[inf2][MAXN];
map <ll, ll> dd;
map <int, pair <ll, ll>> ls;
int mnn = inf;
int pos = inf;
int dep[MAXN];
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
		c[i] += c[i - 1];
	}
	for (int i = n; i >= 0; i--) {
		lst[i] = dd.count(c[i]) ? dd[c[i]] : inf;
		dd[c[i]] = i;
		if (!ls.count(c[i])) ls[c[i]] = {inf, inf};
		swap(ls[c[i]].first, ls[c[i]].second);
		ls[c[i]].second = i;
		if (ls[c[i]].first < mnn) {
			mnn = ls[c[i]].first; pos = ls[c[i]].second;
		}
		pp[i] = pos;
	} 
	dd.clear();
	for (int i = n; i >= 0; i--) {
		if (lst[i] == inf) nxt[0][i] = inf;
		else nxt[0][i] = pp[lst[i]];
		dep[i] = (nxt[0][i] == inf ? 1 : 1 + dep[nxt[0][i]]);
	}
	for (int i = 1; i < inf2; i++) for (int j = 0; j <= n; j++) {
		if (nxt[i - 1][j] == inf) { nxt[i][j] = inf; }
		else nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
	}
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		int cur = pp[l - 1];
		if (cur == inf || lst[cur] > r) {
			cout << "0\n";
			continue;
		}
		for (int i = inf2 - 1; i >= 0; i--) {
			if (nxt[i][cur] != inf && nxt[i][cur] <= r) {
				cur = nxt[i][cur];
			}
		}
		int z = -dep[cur] + dep[pp[l - 1]];
		if (lst[cur] <= r) cur = lst[cur], z++;
		cout << z << '\n';
	}
}
	

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