Submission #1275490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275490		raditya_noor	Fountain (eJOI20_fountain)	C++20	100 / 100	350 ms	26656 KiB

fountain

#include <bits/stdc++.h>
#define sz size
#define em empty
#define psb push_back
#define ppb pop_back
#define ps push
#define pp pop
#define tp top
#define fr first
#define sc second
#define ll long long
using namespace std;
int const MAX_N = 1e5, MAX_Q = 2e5;
vector <pair <ll, int>> pf; 
vector <pair <ll, int>> rv[MAX_N + 1];
ll d[MAX_N + 1] = {0}, c[MAX_N + 1] = {0}; 
vector <int> gr[MAX_N + 1];
int ans[MAX_Q + 1] = {0};


void dfs(int u){
	ll before = 0; if(!pf.em()) before = (*pf.rbegin()).fr;
	pf.psb({c[u] + before, u});
	//do queries
	ll peak = (*pf.rbegin()).fr;
	for(auto [x, y] : rv[u]){
//		cout << y << ' ';
		//binser
		int l = 0, r = pf.sz() - 1, cum;
		while(l <= r){
			int mid = (l + r) / 2;
			if(peak - pf[mid].fr < x){
				cum = pf[mid].sc;
				r = mid - 1;
			}else{
				l = mid + 1;
			}
			
		}
		ans[y] = cum;
	}
	//iterate over next path
	for(auto v : gr[u]){
		dfs(v);
	}
	pf.ppb();
}

int main(){
	//input
	int n, q; cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> d[i] >> c[i];
	
	//graph
	stack <pair <ll, int>> st; st.ps({d[1], 1});
	for(int i = 2; i <= n; i++){
		while(!st.em() && st.tp().fr < d[i]){
			gr[i].psb(st.tp().sc);
			st.pp();
		}
		st.ps({d[i], i});
	}
	while(!st.em()){
		gr[0].psb(st.tp().sc);
		st.pp();
	}
	
//	for(int i = 0; i <= n; i++){
//		cout << i << ": "; for(auto v : gr[i]) cout << v << ' '; cout << '\n';
//	} 
	
	//input queries per node
	for(int i = 1, r; i <= q; i++){
		ll v; cin >> r >> v;
		rv[r].psb({v, i});
	}
	
	//dfs
	
	dfs(0);
	
	for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}

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