oj.uz

Submission #926224

# Submission time Handle Problem Language Result Execution time Memory
926224 2024-02-12T17:34:34 Z ArgoCahaya Fountain (eJOI20_fountain) C++14
100 / 100
 690 ms 127272 KB 
#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

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 5 ms 6492 KB Output is correct
6 Correct 5 ms 6492 KB Output is correct
7 Correct 5 ms 6488 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 123652 KB Output is correct
2 Correct 494 ms 115280 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Correct 5 ms 6492 KB Output is correct
6 Correct 5 ms 6492 KB Output is correct
7 Correct 5 ms 6488 KB Output is correct
8 Correct 462 ms 123652 KB Output is correct
9 Correct 494 ms 115280 KB Output is correct
10 Correct 4 ms 6488 KB Output is correct
11 Correct 224 ms 75072 KB Output is correct
12 Correct 690 ms 127272 KB Output is correct
13 Correct 515 ms 125264 KB Output is correct
14 Correct 416 ms 124756 KB Output is correct
15 Correct 375 ms 124620 KB Output is correct