oj.uz

Submission #831367

# Submission time Handle Problem Language Result Execution time Memory
831367 2023-08-20T07:23:54 Z vito Fountain (eJOI20_fountain) C++
100 / 100
 325 ms 40772 KB 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define F first
#define S second
const ll LOG=18;
const ll MAX=1e5+5;
const ll A=1005;
const ll INF=1e9+5;
ll par[MAX][LOG];
ll sum[MAX][LOG];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, q;
	cin >> n >> q;
	vector<pair<ll, ll>> a(n+1);
	for(ll i=1; i<=n; i++) {
		cin >> a[i].F >> a[i].S;
	}
	sum[n+1][0]=INF;
	a.push_back(make_pair(INF, INF));
	for(ll i=0; i<LOG; i++) {
		par[n+1][i]=n+1;
		sum[n+1][i]=INF;
	}
	set<pair<ll, ll>> s; // (d, index)
	for(ll i=1; i<=n; i++) {
		while(!s.empty() && (*s.begin()).F<a[i].F) {
			auto v=*s.begin();
			s.erase(v);
			par[v.S][0]=i;
			sum[v.S][0]=a[i].S+a[v.S].S;
		}
		s.insert(make_pair(a[i].F, i));
	}
	for(int i=0; i<LOG; i++) {
		par[n+1][i]=0;
	}
	while(!s.empty()) {
		auto v=*s.begin();
		s.erase(v);
		par[v.S][0]=n+1;
		sum[v.S][0]=INF;
	}
	for(ll i=1; i<LOG; i++) {
		for(ll j=1; j<=n; j++) {
			par[j][i]=par[par[j][i-1]][i-1];
		}
	}
	for(ll i=1; i<LOG; i++) {
		for(ll j=1; j<=n; j++) {
			sum[j][i]=min(INF, sum[j][i-1]+sum[par[j][i-1]][i-1]-a[par[j][i-1]].S);
		}
	}
	// for(int i=1; i<=n+1; i++) {
	// 	for(int j=0; j<4; j++) {
	// 		cout << i << ' ' << par[i][j] << '\n';
	// 	}
	// 	cout << '\n';
	// 	for(int j=0; j<4; j++) {
	// 		cout << i << ' ' << sum[i][j] << '\n';
	// 	}
	// 	cout << '\n';
	// }
	while(q--) {
		ll r, v;
		cin >> r >> v;
		// cout << "x=" << a[r].S << '\n';
		if(a[r].S>=v) {
			cout << r;
		}
		else {
			ll ss=a[r].S;
			ll cur=r;
			for(ll i=LOG-1; ~i; i--) {
				if(ss+sum[cur][i]-a[cur].S<v) {
					ss+=sum[cur][i]-a[cur].S;
					cur=par[cur][i];
					// cout << "i=" << i << '\n';
					// cout << "ss=" << ss << '\n';
					// cout << "cur=" << cur << "\n\n";
				}
			}
			int rj=par[cur][0];
			if(rj==n+1) {
				rj=0;
			}
			cout << rj;
		}
		cout << '\n';
		// return 0;
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 476 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 564 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 29404 KB Output is correct
2 Correct 206 ms 30288 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 476 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 564 KB Output is correct
8 Correct 202 ms 29404 KB Output is correct
9 Correct 206 ms 30288 KB Output is correct
10 Correct 1 ms 632 KB Output is correct
11 Correct 76 ms 19360 KB Output is correct
12 Correct 325 ms 35340 KB Output is correct
13 Correct 179 ms 35332 KB Output is correct
14 Correct 151 ms 34160 KB Output is correct
15 Correct 140 ms 40772 KB Output is correct