Submission #880713

#	Time	Username	Problem	Language	Result	Execution time	Memory
880713		Acanikolic	Sum Zero (RMI20_sumzero)	C++14	0 / 100	5 ms	4956 KiB

sumzero

#include <bits/stdc++.h>

#define int long long

#define pb push_back

#define F first

#define S second

using namespace std;

const int N = 1e6 + 10;

const int inf = 1e18;

const int lg = 20;

int a[N],st[N][lg];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	map<int,vector<int>>last;
	int S = 0;
	for(int i = 1; i <= n; i++) {
		S += a[i];
		last[S].pb(i);
	}
	// pref[i] - pref[j-1] == 0
	// 
	int sum = 0;
	for(int i = 1; i <= n; i++) {
		int index = sum;
		sum += a[i];
		if(last[index].empty()) {
			st[i][0] = n + 1;
			continue;
		}
		int l = 0,r = last[index].size() - 1,ans = -1;
		while(l <= r) {
			int mid = (l + r) / 2;
			if(last[index][mid] >= i) {
				ans = mid;
				r = mid - 1;
			}else {
				l = mid + 1;
			}
		}
		if(ans == -1) st[i][0] = n + 1;
		else st[i][0] = last[index][ans];
	}
	for(int i = n - 1; i >= 1; i--) st[i][0] = min(st[i][0],st[i+1][0]);
	for(int j = 1; j < lg; j++) {
		for(int i = 1; i <= n; i++) {
			st[i][j] = st[min(st[i][j-1]+1,n)][j-1];
		}
	}
	for(int i = 1; i <= n; i++) {
	//	for(int j = 0; j < lg; j++) cout << st[i][j] << ' ';
	//	cout << endl;
	}
	int q;
	cin >> q;
	while(q--) {
		int l,r,res = 0;
		cin >> l >> r;
		for(int j = lg - 1; j >= 0; j--) {
			if(st[l][j] <= r && st[l][j] != 0) {
				res += (1 << j);
				l = st[l][j] + 1;
			//	cout << l << ' ' << st[l][0] << endl;
			}
		}
		for(int j = lg - 1; j >= 0; j--) {
			if(st[l][j] <= r && st[l][j] != 0) {
				res += (1 << j);
				l = st[l][j] + 1;
				//cout << l << ' ' << st[l][0] << endl;
			}
		}
		cout << res << '\n';
	}
    return 0;
}

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