oj.uz

Submission #813541

# Submission time Handle Problem Language Result Execution time Memory
813541 2023-08-07T19:57:28 Z Acanikolic Fountain (eJOI20_fountain) C++14
100 / 100
 275 ms 33732 KB 
#include <bits/stdc++.h>
		 				 
#define pb push_back 
		
#define int long long 		
		
#define F first
		 
#define S second
		 
using namespace std;
		 
const int N = 1e5+10;
		 
const int mod = 1e9+7;
		 
const int inf = 1e18;	

const int lg = 18;

int up[N][lg],vis[N];
long long sm[N][lg];
pair<int,int>a[N];
				
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	
	int n,Q;
	cin >> n >> Q;
	for(int i=1;i<=n;i++) cin >> a[i].F >> a[i].S;
	stack<pair<int,int>>st;
	for(int i=1;i<=n;i++) up[i][0] = i;
	for(int i=n;i>=1;i--) {
		while(st.size() && st.top().F <= a[i].F) st.pop();
		if(!st.empty()) {
			up[i][0] = st.top().S;
			sm[i][0] = a[st.top().S].S;
			// /cout << i << " -> " << st.top().S << ' ' << a[st.top().S].S << endl;
			//g[st.top().S].pb(i);
		}
		st.push({a[i].F,i});
	}
	for(int j=1;j<lg;j++) {
		for(int i=1;i<=n;i++) {
			up[i][j] = up[up[i][j-1]][j-1];
			sm[i][j] = sm[i][j-1]+sm[up[i][j-1]][j-1];
		}
	}
	/*for(int i=1;i<=n;i++) {
		for(int j=0;j<lg;j++) cout << sm[i][j] << ' ';
		cout << endl;
	}*/
	while(Q--) {
		int index,val;
		cin >> index >> val;
		val -= a[index].S;
		for(int j=lg-1;j>=0;j--) {
			if(sm[index][j] <= val) {
				//cout << index << ' ' << j << ' ' << val << ' ' << sm[index][j] << endl;
				val -= sm[index][j];
				index = up[index][j];
			}
		}
		if(val > sm[index][0]) {
			cout << "0\n";
			continue;
		}
		if(val > 0) index = up[index][0];
		cout << index << '\n';
	}
    return 0; 
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 30844 KB Output is correct
2 Correct 207 ms 28632 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 181 ms 30844 KB Output is correct
9 Correct 207 ms 28632 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 60 ms 17508 KB Output is correct
12 Correct 275 ms 32880 KB Output is correct
13 Correct 171 ms 33176 KB Output is correct
14 Correct 126 ms 33708 KB Output is correct
15 Correct 110 ms 33732 KB Output is correct