제출 #788792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
788792		ThylOne	Fountain (eJOI20_fountain)	C++14	0 / 100	54 ms	57296 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define debug(var) cerr<<"#"<<#var<<"="<<var<<endl;
#define int long long
const int LOG = 18;
const int MAXI = 2*100000;
struct Recip{
	int diametre;
	int capacite;
	int id;
	void read(int i){
		cin>>diametre;
		cin>>capacite;
		id=i;
	};
};
vector<Recip> recipient;
vector<int> links[MAXI];
int sumFromRoot[MAXI];
int up[MAXI][LOG];
int n,q;

void dfs(int node,int somme=0){
	somme+=recipient[node].capacite;
	sumFromRoot[node] = somme;
	for(int&v:links[node]){
		dfs(v,somme);
	}
}
int ancestorK(int node,int k){
	for(int log=LOG-1;log>=0;log--){
		if((k>>log)&1){
			node = up[node][log];
		}
	}
	return node;
}


int solve2(int id,int volume){
	int sommeChaine = sumFromRoot[id];
	if(sommeChaine<volume){
		return -1;
	}
	int low=0;
	int high=n-1;
	while((high-low)>1){
		int mid = (low+high)/2;
		int pos = ancestorK(id,mid);
		if(pos==-1){
			high=mid;
			continue;
		}
		int somme = sommeChaine-sumFromRoot[pos]+recipient[pos].capacite;
		if(somme>volume){
			high = mid;
		}else if(somme<volume){
			low = mid;			
		}else{
			return pos;
		}
	}
	int LS = sommeChaine-sumFromRoot[ancestorK(id,low)]+recipient[ancestorK(id,low)].capacite;
	if(LS>=volume){
		return ancestorK(id,low);
	}else{
		return ancestorK(id,high);
	}
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   
	cin>>n>>q;
	recipient.resize(n);
	vector<int> pref(n);
	int act=0;
	for(int i = 0 ; i <n;i++){
		recipient[i].read(i);
		act+=recipient[i].capacite;
		pref[i]=act;
	}
	int papa[n];
	for(int i = 0;i<n;i++){
		papa[i]=-1;
	}

	stack<Recip> pile;
	for(int i = 0;i<n;i++){
		while(!pile.empty() && recipient[i].diametre>pile.top().diametre){
			papa[pile.top().id] = i;
			links[i].push_back(pile.top().id);
			pile.pop();
		}
		pile.push(recipient[i]);
	}
	for(int i = 0 ; i<n;i++){
		if(papa[i]==-1){
			dfs(i);
		}
		up[i][0]=papa[i];
	}
	for(int l=1;l<LOG;l++){
		for(int i=0;i<n;i++){
			if(up[i][l-1]==-1){
				up[i][l]=-1;
			}else{
				up[i][l] = up[up[i][l-1]][l-1];
			}
			
		}
	}
	for(int i = 0 ; i < q;i++){
		int id,volume;cin>>id>>volume;
		id--;
		cout<<solve2(id,volume)+1<<endl;
	}
	
	
   
}

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