oj.uz

답안 #495321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
495321 2021-12-18T11:47:50 Z uncripted Fountain (eJOI20_fountain) C++11
100 / 100
 700 ms 40116 KB 
//unfin
#include<bits/stdc++.h>
#define s second
#define f first
using namespace std;
pair<long long,long long> go[100050][20];
long long par[100050];
long long d[100050];
long long c[100050];
int main(){
long long n,q;
cin>>n>>q;

for(long long i=1; i<=n; i++){
cin>>d[i];
cin>>c[i];

}
d[n+1]=INT_MAX;
d[0]=INT_MAX;
stack<long long> s;
s.push(n+1);
for(long long 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(long long i=1; i<20; i++){
	for(long long ii=1; ii<200005; ii++){
	
			go[ii][i].s=long long_MAX;

		
	}
}*/
for(long long i=1; i<20; i++){
	for(long long ii=1; ii<100050; 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;
		}
	}
}
for(long long i=1; i<=q; i++){
	long long x,y;
	cin>>x>>y;
	long long j=19;
	long long st=x;
	if(y>go[st][19].f){
		cout<<0<<endl;
		continue;
	}
	for(j=19; j>=0; j--){
		
		if(y>go[st][j].f){
			y-=go[st][j].f;
			st=go[st][j].s;
		}
		
	}
	cout<<st<<endl;
	
	
}	
	
	
	
	
	
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 31624 KB Output is correct
2 Correct 38 ms 31532 KB Output is correct
3 Correct 44 ms 31652 KB Output is correct
4 Correct 36 ms 31568 KB Output is correct
5 Correct 37 ms 31676 KB Output is correct
6 Correct 40 ms 31688 KB Output is correct
7 Correct 37 ms 31672 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 445 ms 38320 KB Output is correct
2 Correct 518 ms 38312 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 31624 KB Output is correct
2 Correct 38 ms 31532 KB Output is correct
3 Correct 44 ms 31652 KB Output is correct
4 Correct 36 ms 31568 KB Output is correct
5 Correct 37 ms 31676 KB Output is correct
6 Correct 40 ms 31688 KB Output is correct
7 Correct 37 ms 31672 KB Output is correct
8 Correct 445 ms 38320 KB Output is correct
9 Correct 518 ms 38312 KB Output is correct
10 Correct 38 ms 31560 KB Output is correct
11 Correct 260 ms 35260 KB Output is correct
12 Correct 700 ms 40116 KB Output is correct
13 Correct 650 ms 38868 KB Output is correct
14 Correct 508 ms 38000 KB Output is correct
15 Correct 498 ms 37560 KB Output is correct