oj.uz

Submission #909871

# Submission time Handle Problem Language Result Execution time Memory
909871 2024-01-17T14:03:22 Z kachu Fountain (eJOI20_fountain) C++17
100 / 100
 924 ms 18440 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 
#define ofind find_by_order
#define okey order_of_key

#define int long long
#define double long double
#define pque priority_queue
#define dque deque
#define que queue
#define umap unordered_map
#define uset unordered_set
#define pipii pair<int, pair<int,int>>
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define iter iterator
#define endl '\n'
#define MOD 1000000007
#define INF 1e18 

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, Q;
	cin >> N >> Q;
	int D[N + 1], C[N + 1];
	
	for (int i = 1; i <= N; i++)
		cin >> D[i] >> C[i];
	
	int next[N + 1];
	stack<int> st;
	
	for (int i = N; i >= 1; i--){
		while (!st.empty() && D[st.top()] <= D[i])
			st.pop();
		
		if (!st.empty())
			next[i] = st.top();
		else
			next[i] = 0;
		
		st.push(i);
	}
	
	vector<pii> query[N + 1];
	int ans[Q];
	
	for (int i = 0; i < Q; i++){
		int a, x;
		cin >> a >> x;
		query[a].pb(mp(x, i));
	}

	bool visited[N + 1];
	memset(visited, 0, sizeof visited);
	
	for (int i = 1; i <= N; i++){
		if (visited[i]) continue;
		
		pque<pii, vector<pii>, greater<pii>> pq;
		int ptr = i, prev = 0, cap = 0;
		
		while (ptr != 0){
			cap += C[ptr];
			
			if (!visited[ptr])
				for (auto qu : query[ptr])
					pq.push(mp(qu.first + prev, qu.second));
			
			while (!pq.empty() && pq.top().first <= cap){
				int qid = pq.top().second;
				pq.pop();
				ans[qid] = ptr;
			}
			
			visited[ptr] = 1;
			prev += C[ptr];
			ptr = next[ptr];
		}
		
		while (!pq.empty()){
			int qid = pq.top().second;
			pq.pop();
			ans[qid] = 0;
		}
	}
	
	for (int i = 0; i < Q; i++)
		cout << ans[i] << endl;

	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 12032 KB Output is correct
2 Correct 85 ms 12284 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 71 ms 12032 KB Output is correct
9 Correct 85 ms 12284 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 310 ms 6696 KB Output is correct
12 Correct 102 ms 18440 KB Output is correct
13 Correct 924 ms 12940 KB Output is correct
14 Correct 78 ms 13052 KB Output is correct
15 Correct 84 ms 13120 KB Output is correct