oj.uz

답안 #777414

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777414 2023-07-09T08:11:39 Z DangerNoodle7591 Fountain (eJOI20_fountain) C++17
100 / 100
 626 ms 29348 KB 
#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);
//#define endl "\n"
#define ll long long
#define pb push_back
#define N 100005
#define f first
#define s second
#define M 17
int n;
int arr[N],boyut[N];
int buyuk[N];
ll int binali[N][M],cap[N][M];
inline void bibuyuk(){
	stack<pair<int,int>> s;
	for(int i=n;i>0;i--){
		while(s.size()){
			int a=s.top().f,b=s.top().s;
			if(arr[i]>=a)s.pop();
			else {
				buyuk[i]=b;
				break;
			}
		}
		s.push({arr[i],i});
	}
}
inline void binali_lifting(){
	boyut[0]=1000000000;
	for(int i=0;i<=n;i++){
		binali[i][0]=buyuk[i];
		cap[i][0]=boyut[i]+boyut[buyuk[i]];
	}
	for(int i=1;i<M;i++){
		for(int j=0;j<=n;j++){
			int bigger=buyuk[binali[j][i-1]];
			binali[j][i]=binali[bigger][i-1];
			cap[j][i]=cap[j][i-1]+ cap[bigger][i-1] ;
		}
	}
}
int main(){
	int q;cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>arr[i]>>boyut[i];
	bibuyuk();
	binali_lifting();
	while(q--){
		ll int x,y;cin>>x>>y;
		if(y<=boyut[x]){
			cout<<x<<endl;
			continue;
		}
		int yer=x;
		int yes=0;
		while(12){
			int l=0,r=M-1;
			while(l<r){
				int m=(l+r)/2;
				//cout<<cap[yer][m]<<" "<<m<<endl;
				if(cap[yer][m]<y){
					l=m+1;
				}
				else r=m;
			}
			if(l==0){
				break;
			}
			y=y-cap[yer][l-1];
			if(y==0){
				yes=1;
				break;
			}
			yer=binali[yer][l-1];
			y+=boyut[yer];
			//cout<<yer<<" "<<y<<" "<<l<<" "<<r<<endl;
			if(l==0)break;
		}
		if(yes==0)yer=binali[yer][0];
		cout<<yer<<endl;

	}
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 386 ms 27628 KB Output is correct
2 Correct 448 ms 25528 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 386 ms 27628 KB Output is correct
9 Correct 448 ms 25528 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 199 ms 16248 KB Output is correct
12 Correct 626 ms 29348 KB Output is correct
13 Correct 455 ms 29304 KB Output is correct
14 Correct 405 ms 29196 KB Output is correct
15 Correct 377 ms 29236 KB Output is correct