제출 #1272615

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

sumzero

// UUID: cdd0d465-d3b0-40d7-8925-489752bcb103
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int c=4e5+10,gy=500;
int kov[c],ki[c],lep[c];
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n; cin>>n;
	vector<ll> pref(n+1);
	for(int i=1; i<=n; i++)
	{
		int x; cin>>x;
		pref[i]=pref[i-1]+x;
	}
	map<ll, int> ind;
	kov[n+1]=n+1;
	for(int i=n; i>=0; i--)
	{
		kov[i]=kov[i+1];
		if(ind.count(pref[i]))
		{
			kov[i]=min(kov[i],ind[pref[i]]);
		}
		ind[pref[i]]=i;
	}
	for(int i=n; i>=0; i--)
	{
		if(kov[i]>n)
		{
			ki[i]=n+1;
		}
		else
		{
			int x=(i-1)/gy,y=(kov[i]-1)/gy;
			if(x==y) ki[i]=ki[kov[i]],lep[i]=lep[kov[i]]+1;
			else ki[i]=kov[i],lep[i]=1;
		}
	}
	int q; cin>>q;
	while(q--)
	{
		int l,r; cin>>l>>r;
		int ans=0;
		l--;
		while(ki[l]<=r)
		{
			ans+=lep[l],l=ki[l];
		}
		while(kov[l]<=r) ans++,l=kov[l];
		cout<<ans<<"\n";
	}
}

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