Submission #493961

#	Time	Username	Problem	Language	Result	Execution time	Memory
493961		mosiashvililuka	Sum Zero (RMI20_sumzero)	C++14	22 / 100	1085 ms	5256 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,pi,ans[400009],lef,rig,mid,vi;
pair <int, int> p[400009];
pair <long long, int> f[400009];
//vector <int> v[400009];
pair <int, int> v[400009];
//vector <pair <int, int> > vv[400009];
pair <int, pair <int, int> > vv[400009];
void dfs(int q, int w){
	/*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;
	}*/
	lef=0;rig=tes+1;
	while(1){
		if(lef+1>=rig) break;
		mid=(lef+rig)/2;
		if(vv[mid].first>=q){
			rig=mid;
		}else{
			lef=mid;
		}
	}
	for(ii=rig; ii<=tes; ii++){
		if(vv[ii].first!=q) break;
		c=lower_bound(p+1,p+pi+1,make_pair(vv[ii].second.first,0))-p;
		if(c<=pi) ans[vv[ii].second.second]=dep-p[c].second; else ans[vv[ii].second.second]=0;
	}
	pi++;p[pi]={q,dep};
	lef=0;rig=vi+1;
	while(1){
		if(lef+1>=rig) break;
		mid=(lef+rig)/2;
		if(v[mid].first>=q){
			rig=mid;
		}else{
			lef=mid;
		}
	}
	//for(vector <int>::iterator it=v[q].begin(); it!=v[q].end(); it++){
	for(int I=rig; I<=vi; I++){
		if(v[I].first!=q) continue;
		if(v[I].second==w) continue;
		dep++;
		dfs(v[I].second,q);
		dep--;
	}
	//}
	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);
		vi++;v[vi]={g[i],i};
	}
	sort(v+1,v+vi+1);
	cin>>tes;
	for(t=1; t<=tes; t++){
		cin>>l>>r;l++;r++;
		//vv[r].push_back(make_pair(l-1,t));
		vv[t]={r,{l-1,t}};
	}
	sort(vv+1,vv+tes+1);
	dep=1;
	dfs(0,-1);
	for(t=1; t<=tes; t++){
		cout<<ans[t]<<"\n";
	}
	return 0;
}

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