oj.uz

답안 #493924

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493924 2021-12-13T11:46:45 Z mosiashvililuka Sum Zero (RMI20_sumzero) C++14
61 / 100
 75 ms 27648 KB 
#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.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 5 ms 5324 KB Output is correct
3 Correct 6 ms 5276 KB Output is correct
4 Correct 5 ms 5324 KB Output is correct
5 Correct 6 ms 5308 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 5 ms 5324 KB Output is correct
3 Correct 6 ms 5276 KB Output is correct
4 Correct 5 ms 5324 KB Output is correct
5 Correct 6 ms 5308 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 64 ms 12772 KB Output is correct
8 Correct 59 ms 12060 KB Output is correct
9 Correct 75 ms 12064 KB Output is correct
10 Correct 64 ms 12660 KB Output is correct
11 Correct 70 ms 12168 KB Output is correct
12 Correct 70 ms 11972 KB Output is correct

Subtask #3
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5324 KB Output is correct
2 Correct 5 ms 5324 KB Output is correct
3 Correct 6 ms 5276 KB Output is correct
4 Correct 5 ms 5324 KB Output is correct
5 Correct 6 ms 5308 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 64 ms 12772 KB Output is correct
8 Correct 59 ms 12060 KB Output is correct
9 Correct 75 ms 12064 KB Output is correct
10 Correct 64 ms 12660 KB Output is correct
11 Correct 70 ms 12168 KB Output is correct
12 Correct 70 ms 11972 KB Output is correct
13 Runtime error 61 ms 27648 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -