oj.uz

Submission #764055

# Submission time Handle Problem Language Result Execution time Memory
764055 2023-06-23T06:22:38 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 291 ms 36112 KB 
//gm  --- akezhon
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define int long long
#define pb push_back	
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pii pair<int,int> 
using namespace std;
int n, q;
int z;
int sz;
int d[100005];
int c[100005];
int nex[100005][18];
int col[100005][18];
void emash(){
	
	cin >> n >> z;
	for(int i=1; i <= n; i++){
		cin >> d[i] >> c[i];
		col[i][0] = c[i];
	}
	stack <int> q;
	for(int i=n; i >= 1; i--){
		while(q.size() && d[q.top()] <= d[i]){
			q.pop();
		}
		if ( q.size() ){
			int f = q.top();
			nex[i][0] = f;
		}
		q.push(i);
	}
	for(int i=1; i <= 17; i++){
		for(int j=1; j <= n; j++){
			nex[j][i] = nex[nex[j][i-1]][i-1];
			if ( nex[j][i] == nex[j][i-1] ) col[j][i] = 1e10;
			else col[j][i] = col[j][i-1] + col[nex[j][i-1]][i-1];
		}
	}
	int x = z;
	while(x--){
		int a, b;
		cin >> a >> b;
		for(int i=17; i >= 0; i--){
			if ( col[a][i] < b ){
				b -= col[a][i];
				a = nex[a][i];
			}
		}
		cout << a << '\n';
	}
}
signed main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	//freopen("262144.in", "r", stdin);
	//freopen("262144.out", "w", stdout);
	
	int RealName=1;
	//cin >> RealName;
	while(RealName--){
		//cout << "Case " << ++C << ":\n";
		emash();
	}

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 210 ms 30168 KB Output is correct
2 Correct 185 ms 27904 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 210 ms 30168 KB Output is correct
9 Correct 185 ms 27904 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 61 ms 17788 KB Output is correct
12 Correct 291 ms 36112 KB Output is correct
13 Correct 165 ms 34984 KB Output is correct
14 Correct 131 ms 34076 KB Output is correct
15 Correct 116 ms 34356 KB Output is correct