Submission #946112

#	Time	Username	Problem	Language	Result	Execution time	Memory
946112		dubabuba	Sum Zero (RMI20_sumzero)	C++14	61 / 100	989 ms	20776 KiB

sumzero

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

#pragma GCC optimize("O3")

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

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

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

int i, j, n, m;
long long pref;
vector<pii> range;
map<long long, int> mp;
int stab[mxn][LOG];
int pw[LOG];

int main() {
#ifdef LOCAL
	auto start = chrono::high_resolution_clock::now();
#endif

	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	mp[0] = 0;
	for(i = 1; i <= n; i++) {
		cin >> j;
		pref += j;
		auto it = mp.find(pref);
		if(it != mp.end()) {
			stab[it->ss + 1][0] = i;
			range.push_back(MP((*it).ss + 1, i));
		}
		mp[pref] = i;
	}

	mp.clear();

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

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

	pw[0] = 1;
	for(int i = 1; i < LOG; i++)
		pw[i] = pw[i - 1] * base;

	cin >> m;
	int l, r, ans;
	while(m--) {
		cin >> l >> r;
		ans = 0;
		for(j = LOG - 1; j >= 0; j--) {
			while(stab[l][j] > 0 && stab[l][j] <= r) {
				l = stab[l][j] + 1;
				ans += pw[j];
				// cout << j << ' ';
			}
		}
		cout << ans << endl;
	}
#ifdef LOCAL
	auto end = chrono::high_resolution_clock::now();
	for(int i = 0; i <= 20; ++i) cout << '-';
	cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
	return 0;
}

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