제출 #777411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777411		vjudge1	Fountain (eJOI20_fountain)	C++17	100 / 100	631 ms	33404 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40