Submission #926224

#	Time	Username	Problem	Language	Result	Execution time	Memory
926224		ArgoCahaya	Fountain (eJOI20_fountain)	C++14	100 / 100	690 ms	127272 KiB

fountain

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<long long, long long>
#define loop(i,n) for(int i=1;i<=n;i++)
#define loop0(i,n) for(int i=0;i<n;i++)
using namespace std;

//pbds template
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;

//template <class T>
//using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const ll maxn = 100100;
const ll INF = 1e15;
ll val[maxn];
ll d[maxn];
ll binlift[maxn][50]; //ini 0 based jadi turunnya 2^j
ll pref[maxn][100];// ini 1 based karena index 0 buat simpen nilai dia
ll child[maxn];

void solve(){
	ll n,q;
	cin >> n >> q;
	for(int i=1;i<=n;i++){
		cin >> d[i] >> val[i];
	}
	stack<pll> s;
	for(int i=n;i>=1;i--){
		while(!s.empty()&&s.top().fi<=d[i]){
			s.pop();
		}
		if(s.empty()){
			child[i] = -1;
		}
		else child[i] = s.top().se;
		s.push({d[i],i});
	}
	for(int i=0;i<=30;i++){
		binlift[n][i] = -1;
		pref[n][i] = INF;
	}
	ll now;
	ll jump;
	for(int i=n-1;i>=1;i--){
		now = child[i];
		binlift[i][0] = now;
		if(now==-1) pref[i][0] = -1;
		else pref[i][0] = val[now];
		for(int j=1;j<=30;j++){
			if(now == -1){
				binlift[i][j] = -1;
				pref[i][j] = INF;
			}
			else{
				if(pref[now][j-1]==INF) pref[i][j] = INF;
				else pref[i][j] = pref[i][j-1] + pref[now][j-1];
				now = binlift[now][j-1];
				binlift[i][j] = now;
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=0;j<=10;j++){
//			cout << binlift[i][j] << ' ';
//		}
//		cout << endl;
//	}
//	cout << endl;
//	for(int i=1;i<=n;i++){
//		for(int j=0;j<=10;j++){
//			cout << pref[i][j] << ' ';
//		}
//		cout << endl;
//	}
	for(int i=1;i<=q;i++){
		ll a,b;
		cin >> a >> b;
		ll ans = a;
		ll now = a;
		b-= val[now];
		ll idx = 0;
		while(b>0){
//			cout << b << ' ' << now << endl;
			idx++;
			if(idx==20) break;
			ll mx = pref[now][0];
			ll next = binlift[now][0];
			for(int i=1;i<=30;i++){
				if(pref[now][i]<b){
					mx = pref[now][i];
					next = binlift[now][i];
//					cout << "Test " << mx << ' ' << next << endl;
				}
			}
//			cout << "Hasil cari " << mx << ' ' << next << endl;
			b-=mx;
			now = next; 
		}
		ans = now;
		if(ans==-1) cout << "0" << endl;
		else cout << ans << endl;
	}
}

int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	int tc = 1;
//	cin >> tc;
	while(tc--){
	   solve();
	}
}

Compilation message (stderr)

fountain.cpp: In function 'void solve()':
fountain.cpp:49:5: warning: unused variable 'jump' [-Wunused-variable]
   49 |  ll jump;
      |     ^~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40