Submission #946144

#	Time	Username	Problem	Language	Result	Execution time	Memory
946144		dubabuba	Sum Zero (RMI20_sumzero)	C++14	61 / 100	1038 ms	17252 KiB

sumzero

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

#pragma GCC optimize("O3,no-stack-protector,conserve-stack")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")

const int inf = 1e9 + 10;
const int mxn = 4e5 + 10;
const int base = 74;
const int LOG = 3;

long long pref;
map<long long, int> mp;
map<long long, int>::iterator it;
int stab[LOG][mxn], pw[LOG];

int main() {
	int n, m;
	cin >> n;
	pw[0] = 1;
	for(int i = 1; i < LOG; i++)
		pw[i] = pw[i - 1] * base;
	mp[0] = 0;
	memset(stab[0], 0x3f, sizeof stab[0]);
	for(int i = 1, t; i <= n; i++) {
		cin >> t;
		pref += t;
		it = mp.find(pref);
		// cout << i << " = " << pref << endl;
		if(it != mp.end()) {
			stab[0][it->second + 1] = i;
			// cout << it-> second + 1 << ' ' << i << endl;
		}
		mp[pref] = i;
	}

	for(int i = n; i > 0; i--) {
		// if(stab[0][i] == 0)
		// 	stab[0][i] = stab[0][i + 1];
		// else if(stab[0][i + 1] > 0)
		stab[0][i] = min(stab[0][i], stab[0][i + 1]);
	}

	// for(int i = 1; i <= n; i++)
	// 	cout << stab[0][i] << ' ';
	// cout << endl;

	for(int j = 1; j < LOG; j++)
	for(int i = 1; i <= n; i++) {
		int cur = stab[j - 1][i];
		for(int b = 1; b < base; b++)
		if(cur + 1 <= n)
			cur = stab[j - 1][cur + 1];
		else {
			cur = inf;
			break;
		}
		stab[j][i] = cur;
	}

	cin >> m;
	int l, r, ans;
	while(m--) {
		cin >> l >> r;
		ans = 0;
		for(int j = LOG - 1; j >= 0; j--) {
			while(stab[j][l] > 0 && stab[j][l] <= r) {
				l = stab[j][l] + 1;
				ans += pw[j];
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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