Submission #482067

#	Time	Username	Problem	Language	Result	Execution time	Memory
482067		s_samchenko	Fountain (eJOI20_fountain)	C++17	100 / 100	501 ms	102808 KiB

fountain

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 2e5+100;

vector <int> a(N), b(N), d(N);
vector < vector <pii> > g(N);
vector < vector <int> > up(N, vector <int> (20)), sum = up;

void dfs(int v, int pr, int h = 0){
	d[v] = h+1;
	up[v][0] = pr;
	for (auto to : g[v]){
		dfs(to.ff, v, h+1);
		sum[to.ff][0] = to.ss;
	}
}

int get(int r, int v){
	for (int j = 19; j >= 0; --j){
		if (sum[r][j] < v){
			v -= sum[r][j];
			r = up[r][j];
		}
	}
	return r;
}

void solve(){
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
	vector <pii> st; st.pb({inf, 0});
	for (int i = n; i >= 1; --i){
		while (st.back().ff <= a[i]) st.pop_back();
		pii v = st.back();
		g[v.ss].pb({i, b[i]});
		st.pb({a[i], i});
	}
	
	for (int i = 0; i <= n; ++i)
		if (!d[i]) dfs(i, i);
	for (int j = 1; j < 20; ++j)
		for (int i = 0; i <= n; ++i) up[i][j] = up[up[i][j-1]][j-1];
	for (int j = 1; j < 20; ++j)
		for (int i = 0; i <= n; ++i) sum[i][j] = sum[i][j-1] + sum[up[i][j-1]][j-1];
	
	while (q--){
		int r, v;
		cin >> r >> v;
		cout << get(r, v) << '\n';
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while (tt--){
		solve();
		cout << '\n';
	}
}

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