Submission #909175

#	Time	Username	Problem	Language	Result	Execution time	Memory
909175		emptypringlescan	Fountain (eJOI20_fountain)	C++17	100 / 100	152 ms	26564 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
struct node{
	int s,e,m;
	long long val;
	node *l,*r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		val=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void update(int S, long long V){
		if(s==e){
			val=V;
			return;
		}
		if(S<=m) l->update(S,V);
		else r->update(S,V);
		val=l->val+r->val;
	}
	int bsta(long long V){
		if(s==e) return s;
		if(l->val>=V) return l->bsta(V);
		else return r->bsta(V-l->val);
	}
} *root;
int32_t main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
	int n,q;
	cin >> n >> q;
	root=new node(1,n+1);
	pair<long long,long long> arr[n+1];
	for(int i=1; i<=n; i++) cin >> arr[i].first >> arr[i].second;
	vector<pair<long long,int> > mono;
	int ans[q];
	vector<pair<long long,int> > qu[n+1];
	for(int i=0; i<q; i++){
		int x;
		long long y;
		cin >> x >> y;
		qu[x].push_back({y,i});
	}
	for(int i=n; i>0; i--){
		while(!mono.empty()&&mono.back().first<=arr[i].first){
			root->update(mono.back().second,0);
			mono.pop_back();
		}
		mono.push_back({arr[i].first,i});
		root->update(i,arr[i].second);
		for(auto j:qu[i]){
			ans[j.second]=root->bsta(j.first);
		}
	}
	for(int i=0; i<q; i++) cout << (ans[i]==n+1?0:ans[i]) << '\n';
}

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