oj.uz

Submission #909175

# Submission time Handle Problem Language Result Execution time Memory
909175 2024-01-17T05:58:42 Z emptypringlescan Fountain (eJOI20_fountain) C++17
100 / 100
 152 ms 26564 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 628 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 600 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 22056 KB Output is correct
2 Correct 114 ms 21720 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 628 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 103 ms 22056 KB Output is correct
9 Correct 114 ms 21720 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 61 ms 13056 KB Output is correct
12 Correct 152 ms 26564 KB Output is correct
13 Correct 149 ms 24780 KB Output is correct
14 Correct 108 ms 23808 KB Output is correct
15 Correct 136 ms 23888 KB Output is correct