oj.uz

답안 #494919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
494919 2021-12-17T13:48:45 Z uncripted Fountain (eJOI20_fountain) C++11
30 / 100
 526 ms 37044 KB 
//unfin
#include<bits/stdc++.h>
#define s second
#define f first
using namespace std;
pair<int,int> go[200005][20];
int par[100005];

int main(){
int n,q;
cin>>n>>q;
int d[n+10];
int c[n+10];
for(int i=1; i<=n; i++){
cin>>d[i];
cin>>c[i];

}
d[n+1]=INT_MAX;
d[0]=INT_MAX;
stack<int> s;
s.push(n+1);
for(int i=n; i>=1; i--){
	while(d[i]>=d[s.top()]){
		s.pop();
	}
	go[i][0].s=s.top();
	par[s.top()]=i;
	go[i][0].f=c[i];
	s.push(i);
}
for(int i=1; i<20; i++){
	for(int ii=1; ii<200005; ii++){
	
			go[ii][i].s=INT_MAX;

		
	}
}
for(int i=1; i<20; i++){
	for(int ii=0; ii<200005; ii++){
		go[ii][i].f=go[go[ii][i-1].s][i-1].f+go[ii][i-1].f;
		go[ii][i].s=go[go[ii][i-1].s][i-1].s;
		if(ii>n){
			go[ii][i].s=n+1;
		}
		if(ii<50){
			
//		cout<<ii<<" "<<i<<" "<<go[ii][i].f<<" "<<go[ii][i].s<<endl;
		}
		
	}
}
for(int i=1; i<=q; i++){
	int x,y;
	cin>>x>>y;
	int j=19;
	int st=x;
	while(true){
	if(j==0 && y<=go[st][j].f){
		cout<<st<<endl;
		break;
	}
	while(y<go[st][j].f && j>0){
		j--;
	}
	y-=go[st][j].f;
//	cout<<y<<" y"<<endl;
//cout<<j<<" "<<go[st][j].s<<" "<<go[st][j].f<<endl;
//cout<<st<<" "<<j<<endl;
	
	//	cout<<go[go[st][i-1].s][j-1].s<<"bruh "<<endl;
	if(y<=0){
		cout<<par[go[st][j].s]<<endl;
		break;
	}
	//if()
	if(go[st][j].f==0){
		cout<<"0"<<endl;
		break;
	}
		st=go[st][j].s;
		
	}
	
	
	
}	
	
	
	
	
	
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 73 ms 31560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 523 ms 36700 KB Output is correct
2 Correct 526 ms 37044 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 73 ms 31560 KB Output isn't correct
2 Halted 0 ms 0 KB -