oj.uz

Submission #777411

# Submission time Handle Problem Language Result Execution time Memory
777411 2023-07-09T08:11:05 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 631 ms 33404 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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

# Verdict Execution time Memory Grader output
1 Correct 387 ms 30464 KB Output is correct
2 Correct 433 ms 28584 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 387 ms 30464 KB Output is correct
9 Correct 433 ms 28584 KB Output is correct
10 Correct 4 ms 576 KB Output is correct
11 Correct 206 ms 17980 KB Output is correct
12 Correct 631 ms 33404 KB Output is correct
13 Correct 481 ms 32936 KB Output is correct
14 Correct 435 ms 32092 KB Output is correct
15 Correct 387 ms 32416 KB Output is correct