Submission #942333

#	Time	Username	Problem	Language	Result	Execution time	Memory
942333		dubabuba	Sum Zero (RMI20_sumzero)	C++14	22 / 100	225 ms	20764 KiB

sumzero

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

#define int long long
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 stab[mxn][LOG];

signed 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;
	// }

	int t = 0;
	for(int i = 1; i <= n; i++) {
		while(t < range.size() && range[t].ff < i)
			t++;
		if(i <= range[t].ff)
			stab[i][0] = range[t].ss;
	}

	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;
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:59:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   while(t < range.size() && range[t].ff < i)
      |         ~~^~~~~~~~~~~~~~

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