Submission #602053

#	Time	Username	Problem	Language	Result	Execution time	Memory
602053		Fidan	Fountain (eJOI20_fountain)	C++17	100 / 100	915 ms	44764 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=(1e9)+10;
int main(){
	ll n, q, i, j;
	cin>>n>>q;
	vector<ll> v(n+1);
	vector<ll> c(n+1);
	vector<ll> par(n+1);
	par[n]=n;
	
	for(i=0; i<n; i++){
		cin>>v[i]>>c[i];
	}
	
	v[n]=inf, c[n]=inf;
	stack<ll> s1;
	s1.push(n);
	
	for(i=n-1; i>=0; i--){
		while(true){
			if(v[s1.top()]>v[i]) break;
			s1.pop();
		}
		par[i]=s1.top();
		s1.push(i);
	}
	
	vector<vector<ll>> dp1(n+1, vector<ll> (18, 0));
	
	for(i=0; i<n; i++){
		dp1[i][0]=par[i];
	}
	
	for(j=1; j<18; j++){
		for(i=0; i<n; i++){
			dp1[i][j]=dp1[dp1[i][j-1]][j-1];
		}
	}
	
	vector<vector<ll>> dp(n+1, vector<ll> (18, 0));
	
	for(i=0; i<=n; i++){
		dp[i][0]=c[i];
	}
	
	for(j=1; j<18; j++){
		for(i=0; i<=n; i++){
			dp[i][j]=dp[dp1[i][j-1]][j-1]+dp[i][j-1];
		}
	}
	
	while(q--){
		ll m, k;
		cin>>m>>k;
		m--;
		for(i=17; i>=0; i--){
			if(k>dp[m][i]){
				k-=dp[m][i];
				m=dp1[m][i];
			}
		}
		if(m==n) cout<<0<<endl;
		else cout<<m+1<<endl;
	}
	
	return 0;
}

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