제출 #831367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831367		vito	Fountain (eJOI20_fountain)	C++98	100 / 100	325 ms	40772 KiB

fountain

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