Submission #942302

#	Time	Username	Problem	Language	Result	Execution time	Memory
942302		dubabuba	Sum Zero (RMI20_sumzero)	C++14	61 / 100	274 ms	14280 KiB

sumzero

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

typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int LOG = 20;
const int mxn = 1e5 + 10;
const int inf = 1e9 + 10;
vector<pii> range;
int n, m, p[mxn];

void ono_min(int &MIN, int CMP) { if(CMP < MIN) MIN = CMP; }
int inmap(map<int, int> &mp, const int key) {
	auto it = mp.find(key);
	if(it == mp.end()) return -inf;
	return (*it).ss;
}

int tree[mxn * 4];
int stab[mxn][LOG];

void build(int id, int tl, int tr) {
	tree[id] = inf;
	if(tl == tr) return;
	int tm = (tl + tr) / 2;
	build(id * 2 + 1, tl, tm);
	build(id * 2 + 2, tm + 1, tr);
}

void upt(int id, int tl, int tr, int l, int r, int val) {
	// cout << tl << ' ' << tr << " -> " << l << ' ' << r << endl;
	if(tl == l && r == tr) {
		ono_min(tree[id], val);
		return;
	}
	int tm = (tl + tr) / 2;
	if(r <= tm) upt(id * 2 + 1, tl, tm, l, r, val);
	else if(tm < l) upt(id * 2 + 2, tm + 1, tr, l, r, val);
	else {
		upt(id * 2 + 1, tl, tm, l, tm, val);
		upt(id * 2 + 2, tm + 1, tr, tm + 1, r, val);
	}
}

int query(int id, int tl, int tr, int i) {
	if(tl == tr) return tree[id];
	int tm = (tl + tr) / 2;
	if(i <= tm) return min(tree[id], query(id * 2 + 1, tl, tm, i));
	return min(tree[id], query(id * 2 + 2, tm + 1, tr, i));
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> p[i];
		p[i] += p[i - 1];
	}

	map<int, int> mp;
	for(int i = 0; i <= n; i++) {
		int t = inmap(mp, p[i]);
		mp[p[i]] = i;
		if(t == -inf) continue;
		range.push_back(MP(t + 1, i));
		// prv[i] = t + 1;
		// nxt[t + 1] = i;
	}

	build(0, 0, n);
	for(pii r : range) {
		// cout << 0 << ' ' << r.ff << ": " << r.ss << endl;
		upt(0, 0, n, 0, r.ff, r.ss);
	}

	for(int i = 0; i < mxn; i++)
	for(int k = 0; k < LOG; k++)
		stab[i][k] = inf;

	for(int i = 1; i <= n; i++) {
		stab[i][0] = query(0, 0, n, i);
		// cout << i << ": " << stab[i][0] << endl;
	}

	for(int k = 1; k < LOG; k++)
	for(int l = 1; l <= n; l++) {
		int r = stab[l][k - 1];
		if(r + 1 <= n)
			stab[l][k] = stab[r + 1][k - 1];
	}

	cin >> m;
	for(int i = 0; i < m; i++) {
		int l, r, ans = 0;
		cin >> l >> r;

		for(int k = LOG - 1; k >= 0; k--) {
			int mid = stab[l][k];
			if(mid <= r) {
				// cout << l << ' ' << r << " = " << (1 << k) << " + " << mid + 1 << ' ' << r << endl;
				l = mid + 1;
				ans ^= (1 << k);
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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