Submission #463310

#	Time	Username	Problem	Language	Result	Execution time	Memory
463310		amunduzbaev	Fountain (eJOI20_fountain)	C++14	100 / 100	479 ms	40084 KiB

fountain

#include "bits/stdc++.h"
using namespace std;

#define int long long

void solve(){
	int n, q; cin>>n>>q;
	vector<array<int, 20>> par(n),  sum(n);
	vector<array<int, 2>> a(n), ss;
	for(int i=0;i<n;i++) cin>>a[i][0]>>a[i][1], par[i][0] = i, sum[i][0] = 0;
	
	ss.push_back({(int)(1e9+1), n});
	for(int i=n-1;~i;i--){
		while(ss.back()[0] <= a[i][0]) ss.pop_back();
		par[i][1] = ss.back()[1];
		sum[i][1] = a[i][1];
		ss.push_back({a[i][0], i});
	}

	for(int j=2;j<20;j++){
		for(int i=0;i<n;i++){
			if(par[i][j-1] < n) par[i][j] = par[par[i][j-1]][j-1];
			else par[i][j] = n;
		}
	}
	
	//~ for(int i=0;i<n;i++) cout<<sum[i][0]<<" ";
	//~ cout<<"\n";
	//~ for(int i=0;i<n;i++) cout<<sum[i][1]<<" ";
	//~ cout<<"\n";
	
	for(int j=2;j<20;j++){
		for(int i=0;i<n;i++){
			if(par[i][j-1] < n){
				sum[i][j] = sum[i][j-1] + sum[par[i][j-1]][j-1];
			} else {
				sum[i][j] = sum[i][j-1];
			}
		}
		
		//~ for(int i=0;i<n;i++) cout<<sum[i][j]<<" ";
		//~ cout<<"\n";
	}
	
	//~ cout<<"\n";
	
	while(q--){
		int i, add; cin>>i>>add, i--;
		for(int j=19;~j;j--){
			
			//~ cout<<i<<" "<<sum[i][j]<<"\n";
			
			if(sum[i][j] < add){
				add -= sum[i][j];
				i = par[i][j];
			}
			
			if(i == n){
				break;
			}
		}
		
		if(i == n){
			cout<<0<<"\n";
		} else {
			cout<<i + 1<<"\n";
		}
	}
}

/*

6 5
4 10
6 8
3 5
4 14
10 9
4 20

1 25
6 30
5 8
3 13
2 8

*/

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t = 1;
	//~ cin>>t;
	while(t--) solve();
}

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