Submission #824127

#	Time	Username	Problem	Language	Result	Execution time	Memory
824127		vanic	Fountain (eJOI20_fountain)	C++14	100 / 100	133 ms	20040 KiB

fountain

#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

const int maxn=1e5+5, Log=17;

int parent[maxn][Log];
int val[maxn][Log];
int d[maxn];
stack < pair < int, int > > s;
int n, q;

int solve(int x, int v){
	for(int i=Log-1; i>-1; i--){
		if(val[x][i]<v){
			v-=val[x][i];
			x=parent[x][i];
		}
	}
	return x;
}

void precompute(){
	for(int i=1; i<Log; i++){
		for(int j=0; j<=n; j++){
			parent[j][i]=parent[parent[j][i-1]][i-1];
			if(parent[j][i]!=parent[j][i-1]){
				val[j][i]=val[j][i-1]+val[parent[j][i-1]][i-1];
			}
			else{
				val[j][i]=val[j][i-1];
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for(int i=0; i<n; i++){
		cin >> d[i] >> val[i][0];
	}
	val[n][0]=1e9;
	parent[n][0]=n;
	s.push({2e9, n});
	for(int i=n-1; i>-1; i--){
		while(s.top().first<=d[i]){
			s.pop();
		}
		parent[i][0]=s.top().second;
		s.push({d[i], i});
	}
	precompute();
	int sol;
	int r, v;
	for(int i=0; i<q; i++){
		cin >> r >> v;
		sol=solve(r-1, v);
		cout << (sol+1)%(n+1) << '\n';
	}
	return 0;
}

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