Submission #1175419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175419		algoproclub	Fountain (eJOI20_fountain)	C++20	60 / 100	607 ms	589824 KiB

fountain

// UUID: b1775b30-3828-452d-b6b3-3dcbe9c2733a
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;cin>>n>>q;
	vector<int> a(n);
	vector<int> c(n);
	vector<int> hova(n, -1);
	stack<int> s;
	for(int i=0;i<n;i++){
		cin>>a[i]>>c[i];
		while(!s.empty() && a[s.top()]<a[i]){
			hova[s.top()]=i;
			s.pop();
		}
		s.push(i);
	}
	vector<vector<long long>> prefix(n);
	vector<vector<int>> index(n);
	vector<bool> visited(n);
	vector<int> holtalalom(n, -1);
	vector<int> hanyadikban(n, -1);
	for(int i=0;i<n;i++){
		if(visited[i]){
			continue;
		}else{
			prefix[i].push_back(0);
			index[i].push_back(0);
			visited[i]=true;
			int x=i;
			while(x!=-1){
				prefix[i].push_back(c[x]+prefix[i].back());
				index[i].push_back(x);
				x=hova[x];
				if (x == -1) break;
				visited[x]=true;
				holtalalom[x]=i;
				hanyadikban[x]=prefix[i].size()-1;
			}
		}
	}
	while(q--){
		int x, y;cin>>x>>y;
		if(holtalalom[x-1]!=-1){
			int h=holtalalom[x-1], z=hanyadikban[x-1];
			int ossz=prefix[h][z];
			y+=ossz;
			int hi=lower_bound(prefix[h].begin(), prefix[h].end(), y)-prefix[h].begin();
			// cout << h << " " << z << " " << ossz << " " << y << " " << hi;
			// cout << endl;
			// for (int aa : prefix[h]) cout << aa << " ";
			// cout << endl;
			// for (int aa : index[h]) cout << aa << " ";
			// cout << endl<<endl;
			if(hi==prefix[h].size()){
				cout<<0<<'\n';
			}else{
				cout<<index[h][hi]+1<<'\n';
			}
		}else{
			int hi=lower_bound(prefix[x-1].begin(), prefix[x-1].end(), y)-prefix[x-1].begin();
			if(hi==prefix[x-1].size()){
				cout<<0<<'\n';
			}else{
				cout<<index[x-1][hi]+1<<'\n';
			}
		}
	}
}

// prefix: 0 10 18 27 
// index:  0  1  2  5

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