제출 #1272606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272606		algoproclub	Sum Zero (RMI20_sumzero)	C++20	61 / 100	436 ms	75268 KiB

sumzero

// UUID: 138309eb-f5ca-4339-8308-550a1fea64ab
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int c=4e5+10,k=19;
int kov[c][k];
signed main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin>>n;
	vector<int> pref(n+1);
	for(int i=1; i<=n; i++)
	{
		int x; cin>>x;
		pref[i]=pref[i-1]+x;
	}
	map<int, int> ind;
	kov[n+1][0]=n+1;
	for(int i=n; i>=0; i--)
	{
		kov[i][0]=kov[i+1][0];
		if(ind.count(pref[i]))
		{
			kov[i][0]=min(kov[i][0],ind[pref[i]]);
		}
		ind[pref[i]]=i;
	}
	for(int j=0; j<k; j++)
		kov[n+1][j]=n+1;
	for(int j=1; j<k; j++)
		for(int i=0; i<=n; i++)
			kov[i][j]=kov[kov[i][j-1]][j-1];
	int q; cin>>q;
	while(q--)
	{
		int l,r; cin>>l>>r;
		int ans=0;
		l--;
		for(int i=k-1; i>=0; i--)
		{
			if(kov[l][i]<=r)
			{
				ans+=(1<<i);
				l=kov[l][i];
			}
		}
		cout<<ans<<"\n";
	}
}

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