Submission #1129876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129876		heey	Fountain (eJOI20_fountain)	C++20	100 / 100	241 ms	20864 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), prev(n+1, 0);
	for(int i = 0; i <= n; i++) prev[i] = i;

	vector<int> sm(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;
			prev[next[i]] = i;
		}
		s.push({a[i].first, i});
	}

	for(int i = n; i > 0; i--){
		sm[i] = sm[next[i]] + a[i].second;
	}

	vector<vector<int>> up(n+1, vector<int>(32));
	for(int i = n; i > 0; i--){
		up[i][0] = next[i];
		for(int l = 1; l <= 32; l++){
			up[i][l] = up[up[i][l-1]][l-1];
		}
	}


	for(int i = 0; i < q; i++){
		int r, v; cin >> r >> v;
		int cap = sm[r];
		if(a[r].second >= v) cout << r << '\n';
		else{
			for(int l = 32; l >= 0; l--){
				//cout << "xd nigga " << up[r][l];
				
				if(cap - sm[up[r][l]] + a[up[r][l]].second < v)
					r = up[r][l];
			}
			cout << up[r][0] << '\n';
		}
	}
	return 0;
}

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