제출 #911077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
911077		Wendidiask	Fountain (eJOI20_fountain)	C++14	0 / 100	239 ms	48996 KiB

fountain

/*
  ____       _      _                  _                    _               _                        _     _                  _          _____ _     _             
 |  _ \     (_)    | |                (_)                  | |             (_)                      | |   | |                (_)        / ____| |   (_)            
 | |_) | ___ _  ___| |__   ___ _ __    _ ___    __ _    ___| | __ _ ___ ___ _  ___   _ __  _ __ ___ | |__ | | ___ _ __ ___    _ _ __   | |    | |__  _ _ __   __ _ 
 |  _ < / _ \ |/ __| '_ \ / _ \ '_ \  | / __|  / _` |  / __| |/ _` / __/ __| |/ __| | '_ \| '__/ _ \| '_ \| |/ _ \ '_ ` _ \  | | '_ \  | |    | '_ \| | '_ \ / _` |
 | |_) |  __/ | (__| | | |  __/ | | | | \__ \ | (_| | | (__| | (_| \__ \__ \ | (__  | |_) | | | (_) | |_) | |  __/ | | | | | | | | | | | |____| | | | | | | | (_| |
 |____/ \___|_|\___|_| |_|\___|_| |_| |_|___/  \__,_|  \___|_|\__,_|___/___/_|\___| | .__/|_|  \___/|_.__/|_|\___|_| |_| |_| |_|_| |_|  \_____|_| |_|_|_| |_|\__,_|
                                                                                    | |                                                                            
                                                                                    |_|                                                                            
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define debug(x) cerr << #x << " is " << x << "\n";
#define hehe ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repb(i, a, b) for (int i = b; i >= a; i--)
#define pii pair<int, int>
#define f first
#define s second
#define endl '\n'
const int MS = 1e5, LOG = 20;
pii twok[MS][LOG]; // {2^kth parent, distance to 2^kth parent};
int d[MS], c[MS], nearest[MS];
vector<int> adj[MS];
void dfs(int x, int par) {
	for (int k = 0; k < LOG; k++) {
		if (twok[x][k].f == -1) break;
		if (twok[twok[x][k].f][k].f != -1) twok[x][k+1] = {twok[twok[x][k].f][k].f, twok[x][k].s+twok[twok[x][k].f][k].s};
	}
	for (auto u : adj[x]) {
		if (u == par) continue;
		twok[u][0] = {x, c[u]};
		dfs(u, x);
	}
}
int query(int r, int v) {
	if (r == 0) return r;
	for (int k = LOG-1; k >= 0; k--) {
		if (twok[r][k].f != -1 and twok[r][k].s <= v) {
			return query(twok[r][k].f, v-twok[r][k].s);
		} 
	}
	return r;
}
void solve() {
	int n, q; cin >> n >> q;
	
	for (int i = 1; i <= n; i++) cin >> d[i] >> c[i];
	vector<int> v;
	for (int i = 1; i <= n; i++) {
		if (v.empty()) {v.push_back(i); continue;}
		while (!v.empty() and d[v.back()] < d[i]) {
			nearest[v.back()] = i;
			v.pop_back();
		}
		v.push_back(i);
	}
	for (auto i : v) nearest[i] = 0;
	for (int i = 1; i <= n; i++) {
		adj[i].push_back(nearest[i]);
		adj[nearest[i]].push_back(i);
	}
	/*for (int i = 0; i <= n; i++) {
		cout << i << ": ";
		for (auto p : adj[i]) cout << "(" << p.f << ", " << p.s << ") ";
		cout << "\n";
	}*/
	for (int i = 0; i < MS; i++) {
		for (int j = 0; j < LOG; j++) twok[i][j] = {-1, 1e18};
	}
	dfs(0, -1);
	//cout << "---------------------------------------------------------------\n";
	while (q--) {
		int r, v;
		cin >> r >> v;
		cout << query(r, v) << '\n';
	}
}
int32_t main() {
	hehe
	int tc = 1;
	//cin >> tc;
	while (tc--) {solve();}
}

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