Submission #946189

#	Time	Username	Problem	Language	Result	Execution time	Memory
946189		dubabuba	Sum Zero (RMI20_sumzero)	C++14	100 / 100	951 ms	19532 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")

typedef long long i64;
const int mxn = 4e5 + 2;
const int base = 74;
const int LOG = 3;

int n, m, pw[LOG];
int stab[LOG][mxn];
map<i64, int> mp;
map<i64, int>::iterator it;

int i, j, k, t, b;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	mp[0] = 0;
	long long pref = 0;
	fill(stab[0], stab[0] + n + 2, n + 1);
	for(t, i = 1; i <= n; i++) {
		cin >> t;
		pref += t;
		it = mp.find(pref);
		if(it != mp.end()) {
			// cout << it->second << ' ' << i << endl;
			stab[0][it->second] = i;
		}
		mp[pref] = i;
	}

	for(i = n; i >= 0; i--)
		stab[0][i] = min(stab[0][i], stab[0][i + 1]);

	pw[0] = 1;
	int cur;
	for(k = 1; k < LOG; k++) {
		fill(stab[k], stab[k] + n + 2, n + 1);
		pw[k] = pw[k - 1] * base;
		for(i = 0; i <= n; i++) {
			cur = stab[k - 1][i];
			for(b = 1; b < base; b++)
				cur = stab[k - 1][cur];
			stab[k][i] = cur;
			// cout << i << ' ' << k << ": " << cur << endl;
		}
	}

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

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:24:6: warning: left operand of comma operator has no effect [-Wunused-value]
   24 |  for(t, i = 1; i <= n; i++) {
      |      ^

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