oj.uz

Submission #947225

# Submission time Handle Problem Language Result Execution time Memory
947225 2024-03-15T17:56:40 Z ArgoCahaya Fountain (eJOI20_fountain) C++14
100 / 100
 703 ms 127292 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 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 4 ms 6600 KB Output is correct
5 Correct 6 ms 6492 KB Output is correct
6 Correct 5 ms 6600 KB Output is correct
7 Correct 4 ms 6492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 123540 KB Output is correct
2 Correct 502 ms 115280 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 4 ms 6600 KB Output is correct
5 Correct 6 ms 6492 KB Output is correct
6 Correct 5 ms 6600 KB Output is correct
7 Correct 4 ms 6492 KB Output is correct
8 Correct 492 ms 123540 KB Output is correct
9 Correct 502 ms 115280 KB Output is correct
10 Correct 5 ms 6492 KB Output is correct
11 Correct 238 ms 75352 KB Output is correct
12 Correct 703 ms 127292 KB Output is correct
13 Correct 535 ms 125264 KB Output is correct
14 Correct 435 ms 124320 KB Output is correct
15 Correct 375 ms 124500 KB Output is correct