제출 #758285

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
758285		ihceker	Fountain (eJOI20_fountain)	C++14	100 / 100	777 ms	38336 KiB

fountain

#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

const int inf=1e15;

int par[100005][20],arr[100005][20];

int32_t main(){
	int n,q;
	cin>>n>>q;
	int a[n+5],b[n+5];
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	a[n+1]=inf;
	b[n+1]=inf;
	for(int i=1;i<=n+1;i++)arr[i][0]=b[i];
	stack<int>s;
	for(int i=1;i<=n+1;i++){
		while(!s.empty() && a[s.top()]<a[i]){
			par[s.top()][0]=i;

			s.pop();
		}
		s.push(i);
	}
	for(int j=1;j<=19;j++){
		for(int i=1;i<=n+1;i++){
			par[i][j]=par[par[i][j-1]][j-1];
			arr[i][j]=arr[i][j-1]+arr[par[i][j-1]][j-1];
		}
	}
	while(q--){
		int x,y;
		cin>>x>>y;
		for(int i=19;i>=0;i--){
			if(y>arr[x][i]){
				y-=arr[x][i];
				x=par[x][i];
			}
		}
		cout<<(x==n+1?0:x)<<endl;
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40