Submission #1173808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173808		therickyzhang	Sum Zero (RMI20_sumzero)	C++20	100 / 100	381 ms	22336 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 4e5 + 5;
int n,q;
ll* a = new ll[mxN];
pair<ll,int>* b = new pair<ll,int>[mxN];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i] += a[i - 1];
		b[i] = {a[i], i};
	}
	b[0] = {0, 0};
	sort(b, b + n + 1);
	for(int i = 0; i < n; i++){
		if(b[i].first == b[i + 1].first) a[b[i].second] = b[i + 1].second;
		else a[b[i].second] = n + 1;
	}
	a[b[n].second] = n + 1;
	delete[] b;
	int sz = 12;
	int p[n + 5][sz];
	for(int i = 0; i <= n; i++) p[i][0] = a[i];
	delete[] a;
	for(int i = 0; i < sz; i++) p[n + 1][i] = n + 1; 
	for(int i = n; i >= 0; i--){
		p[i][0] = min(p[i][0], p[i + 1][0]);
		for(int j = 1; j < sz; j++) p[i][j] = p[p[i][j - 1]][j - 1];
	}
	cin >> q;
	int l,r,ans;
	while(q--){
		cin >> l >> r;
		ans = 0;
		l--;
		for(int i = sz - 1; i >= 0; i--){
			while(p[l][i] <= r){
				l = p[l][i];
				ans += (1 << i);
			}
		}
		cout << ans << '\n';
	}
}
 

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