Submission #493924

#	Time	Username	Problem	Language	Result	Execution time	Memory
493924		mosiashvililuka	Sum Zero (RMI20_sumzero)	C++14	61 / 100	75 ms	27648 KiB

sumzero

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,g[400009],l,r,dep[400009],pi,ans[400009];
pair <int, int> p[400009];
pair <long long, int> f[400009];
vector <int> v[100009];
vector <pair <int, int> > vv[100009];
void dfs(int q, int w){
	if(q==0){
		dep[q]=1;
	}else{
		dep[q]=dep[w]+1;
	}
	for(vector <pair <int, int> >::iterator it=vv[q].begin(); it!=vv[q].end(); it++){
		c=lower_bound(p+1,p+pi+1,make_pair((*it).first,0))-p;
		if(c<=pi) ans[(*it).second]=dep[q]-p[c].second; else ans[(*it).second]=0;
	}
	pi++;p[pi]={q,dep[q]};
	for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		dfs((*it),q);
	}
	pi--;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	g[1]=0;
	f[0].first=0;f[0].second=1;
	for(i=1; i<=a; i++){
		cin>>f[i].first;f[i].first+=f[i-1].first;f[i].second=i+1;
		/*g[i+1]=m[f[i]];
		m[f[i]]=i+1;*/
	}
	sort(f,f+a+1);
	for(i=1; i<=a; i++){
		if(f[i].first==f[i-1].first){
			g[f[i].second]=f[i-1].second;
		}else{
			g[f[i].second]=0;
		}
	}
	for(i=1; i<=a+1; i++){
		g[i]=max(g[i],g[i-1]);
		v[g[i]].push_back(i);
	}
	cin>>tes;
	for(t=1; t<=tes; t++){
		cin>>l>>r;l++;r++;
		vv[r].push_back(make_pair(l-1,t));
	}
	dfs(0,-1);
	for(t=1; t<=tes; t++){
		cout<<ans[t]<<"\n";
	}
	return 0;
}

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