제출 #894458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894458		iskhakkutbilim	Fountain (eJOI20_fountain)	C++17	100 / 100	418 ms	46932 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()
#define ff first
#define ss second
const int N = 2e6;
const int mod = 1e10;




signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q; cin >> n >> q;
	vector<int> d(n + 1), c(n + 1);
	for(int i = 1;i <= n; i++){
		cin >> d[i] >> c[i];
	}
	d[0] = mod, c[0] = mod;
	stack<pair<int, int> > st;
	st.push({d[0], 0});
	vector<int> right(n+1);
	right[0] = 0;
	for(int i = n; i >= 1; i--){
		while(st.top().ff <= d[i]){
			st.pop();
		}
		right[i] = st.top().ss;
		st.push({d[i], i});
	}
	vector< vector<int> > up(n+1, vector<int>(20));
	vector< vector<int> > sum(n+1, vector<int>(20, 0));
	
	for(int i = 0;i <= n; i++){
		up[i][0] = right[i];
		sum[i][0] = c[right[i]];
	}
	for(int j = 1;j < 20; j++){
		for(int i = 0;i <= n; i++){
			up[i][j] = up[up[i][j-1]][j-1];
			sum[i][j] = sum[up[i][j-1]][j-1] + sum[i][j-1];
		}
	}

	/*
	for(int i = 0;i <= n; i++){
		
		cout << "vertex : " << i << '\n';
		for(int j = 0;j < 4; j++){
			cout << "up to " << (1<<j) << " :: " << up[i][j] << ' ' << sum[i][j] << '\n';
		}
	}
	*/
	while(q--){
		int r, v; cin >> r >> v;
		if(c[r] >= v){
			cout << r << '\n';
			continue;
		}
		v-= c[r];
		
		
		for(int i = 19; i >= 0; i--){
			if(v >= sum[r][i]){
				v-= sum[r][i];
				r = up[r][i];
			}
		}
		if(v == 0){
			cout << r << '\n';
		}else{
			cout << up[r][0] << '\n';
		}
	}
	
	
	
	return 0;
}

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