Submission #495321

#	Time	Username	Problem	Language	Result	Execution time	Memory
495321		uncripted	Fountain (eJOI20_fountain)	C++11	100 / 100	700 ms	40116 KiB

fountain

//unfin
#include<bits/stdc++.h>
#define s second
#define f first
using namespace std;
pair<long long,long long> go[100050][20];
long long par[100050];
long long d[100050];
long long c[100050];
int main(){
long long n,q;
cin>>n>>q;

for(long long i=1; i<=n; i++){
cin>>d[i];
cin>>c[i];

}
d[n+1]=INT_MAX;
d[0]=INT_MAX;
stack<long long> s;
s.push(n+1);
for(long long i=n; i>=1; i--){
	while(d[i]>=d[s.top()]){
		s.pop();
	}
	go[i][0].s=s.top();
	par[s.top()]=i;
	go[i][0].f=c[i];
	s.push(i);
}
/*
for(long long i=1; i<20; i++){
	for(long long ii=1; ii<200005; ii++){
	
			go[ii][i].s=long long_MAX;

		
	}
}*/
for(long long i=1; i<20; i++){
	for(long long ii=1; ii<100050; ii++){
		go[ii][i].f=go[go[ii][i-1].s][i-1].f+go[ii][i-1].f;
		go[ii][i].s=go[go[ii][i-1].s][i-1].s;
		if(ii>n){
			go[ii][i].s=n+1;
		}
	}
}
for(long long i=1; i<=q; i++){
	long long x,y;
	cin>>x>>y;
	long long j=19;
	long long st=x;
	if(y>go[st][19].f){
		cout<<0<<endl;
		continue;
	}
	for(j=19; j>=0; j--){
		
		if(y>go[st][j].f){
			y-=go[st][j].f;
			st=go[st][j].s;
		}
		
	}
	cout<<st<<endl;
	
	
}	
	
	
	
	
	
}

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