Submission #1127864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127864		heey	Fountain (eJOI20_fountain)	C++20	30 / 100	1594 ms	2432 KiB

fountain

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

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	vector<pair<int,int>> a(n+1);
	for(int i = 1; i <= n; i++) {
		int d, c; cin >> d >> c;
		a[i] = {d, c};
	}

	vector<int> next(n+1, 0);
	stack<pair<int,int>> s;
	for(int i = n; i > 0; i--){
		while(!s.empty() && s.top().first <= a[i].first) s.pop();
		if(!s.empty()) next[i] = s.top().second;
		s.push({a[i].first, i});
	}

	for(int i = 0; i < q; i++){
		int r, v; cin >> r >> v;
		while(r != 0 && v > 0) {
            //cout << "v: " << v << " losing: " << a[r].second << " from " << r << ' ';
			v -= a[r].second;
            //cout << "v is now: " << v << " next is " << next[r] << '\n';

            if(v > 0) r = next[r];
		}
		cout << r << '\n';
	}
	return 0;
}

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