Submission #912925

#	Time	Username	Problem	Language	Result	Execution time	Memory
912925		penguin133	Fountain (eJOI20_fountain)	C++17	100 / 100	438 ms	70988 KiB

fountain

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

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int par[20][200005], n, q, sm[20][200005], A[200005], D[200005];

void solve(){
	cin >> n >> q;
	for(int i=1;i<=n;i++)cin >> D[i] >> A[i];
	A[n + 1] = 1e10;
	D[n + 1] = 1e10;
	stack <int> s;
	s.push(n + 1);
	for(int i=n;i>=1;i--){
		while(!s.empty() && D[s.top()] <= D[i])s.pop();
		par[0][i] = s.top(); sm[0][i] = A[i] + A[s.top()];
		s.push(i);
	}
	par[0][n+1] = n + 1; sm[0][n+1] = 1e10;
	for(int i=1;i<=19;i++)for(int j=1;j<=n+1;j++){
		par[i][j] = par[i-1][par[i-1][j]];
		sm[i][j] = sm[i-1][j] + sm[i-1][par[i-1][j]] - A[par[i-1][j]];
		assert(sm[i][j] >= 0);
	}
	while(q--){
		int x, v; cin >> x >> v;
		if(v <= A[x]){
			cout << x << '\n';
			continue;
		}
		int cur = x;
		for(int i = 19; i >= 0; i--){
			if(sm[i][cur] < v){
				v -= (sm[i][cur] - A[par[i][cur]]);
				cur = par[i][cur];
			}
		}
		cur = par[0][cur];
		cout << (cur == n + 1 ? 0 : cur) << '\n';
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

fountain.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main(){
      | ^~~~

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