Submission #764055

#	Time	Username	Problem	Language	Result	Execution time	Memory
764055		vjudge1	Fountain (eJOI20_fountain)	C++17	100 / 100	291 ms	36112 KiB

fountain

//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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40