oj.uz

Submission #493923

# Submission time Handle Problem Language Result Execution time Memory
493923 2021-12-13T11:45:45 Z mosiashvililuka Sum Zero (RMI20_sumzero) C++14
61 / 100
 90 ms 18620 KB 
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,g[100009],l,r,dep[100009],pi,ans[100009];
pair <int, int> p[100009];
pair <long long, int> f[100009];
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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 6 ms 5324 KB Output is correct
3 Correct 5 ms 5324 KB Output is correct
4 Correct 4 ms 5364 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 6 ms 5324 KB Output is correct
3 Correct 5 ms 5324 KB Output is correct
4 Correct 4 ms 5364 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 67 ms 12760 KB Output is correct
8 Correct 63 ms 13748 KB Output is correct
9 Correct 90 ms 13592 KB Output is correct
10 Correct 65 ms 14144 KB Output is correct
11 Correct 64 ms 13756 KB Output is correct
12 Correct 66 ms 13600 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 6 ms 5324 KB Output is correct
3 Correct 5 ms 5324 KB Output is correct
4 Correct 4 ms 5364 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 67 ms 12760 KB Output is correct
8 Correct 63 ms 13748 KB Output is correct
9 Correct 90 ms 13592 KB Output is correct
10 Correct 65 ms 14144 KB Output is correct
11 Correct 64 ms 13756 KB Output is correct
12 Correct 66 ms 13600 KB Output is correct
13 Runtime error 38 ms 18620 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -