oj.uz

Submission #894458

# Submission time Handle Problem Language Result Execution time Memory
894458 2023-12-28T10:00:03 Z iskhakkutbilim Fountain (eJOI20_fountain) C++17
100 / 100
 418 ms 46932 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()
#define ff first
#define ss second
const int N = 2e6;
const int mod = 1e10;




signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q; cin >> n >> q;
	vector<int> d(n + 1), c(n + 1);
	for(int i = 1;i <= n; i++){
		cin >> d[i] >> c[i];
	}
	d[0] = mod, c[0] = mod;
	stack<pair<int, int> > st;
	st.push({d[0], 0});
	vector<int> right(n+1);
	right[0] = 0;
	for(int i = n; i >= 1; i--){
		while(st.top().ff <= d[i]){
			st.pop();
		}
		right[i] = st.top().ss;
		st.push({d[i], i});
	}
	vector< vector<int> > up(n+1, vector<int>(20));
	vector< vector<int> > sum(n+1, vector<int>(20, 0));
	
	for(int i = 0;i <= n; i++){
		up[i][0] = right[i];
		sum[i][0] = c[right[i]];
	}
	for(int j = 1;j < 20; j++){
		for(int i = 0;i <= n; i++){
			up[i][j] = up[up[i][j-1]][j-1];
			sum[i][j] = sum[up[i][j-1]][j-1] + sum[i][j-1];
		}
	}

	/*
	for(int i = 0;i <= n; i++){
		
		cout << "vertex : " << i << '\n';
		for(int j = 0;j < 4; j++){
			cout << "up to " << (1<<j) << " :: " << up[i][j] << ' ' << sum[i][j] << '\n';
		}
	}
	*/
	while(q--){
		int r, v; cin >> r >> v;
		if(c[r] >= v){
			cout << r << '\n';
			continue;
		}
		v-= c[r];
		
		
		for(int i = 19; i >= 0; i--){
			if(v >= sum[r][i]){
				v-= sum[r][i];
				r = up[r][i];
			}
		}
		if(v == 0){
			cout << r << '\n';
		}else{
			cout << up[r][0] << '\n';
		}
	}
	
	
	
	return 0;
}

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 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 44196 KB Output is correct
2 Correct 267 ms 40788 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 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 267 ms 44196 KB Output is correct
9 Correct 267 ms 40788 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 88 ms 24916 KB Output is correct
12 Correct 418 ms 46932 KB Output is correct
13 Correct 266 ms 45136 KB Output is correct
14 Correct 186 ms 44856 KB Output is correct
15 Correct 141 ms 44780 KB Output is correct