제출 #911812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
911812		Wendidiask	Fountain (eJOI20_fountain)	C++14	100 / 100	889 ms	34148 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 linebreak cout << "---------------------------------------------------------\n";
const int MS = 1e5+5, LOG = 20;
int twok[MS][LOG], d[MS], c[MS], nearest[MS], pref[MS];
vector<int> adj[MS];
void dfs(int x, int par) {
	for (int k = 0; k < LOG; k++) {
		if (twok[x][k] == -1) break;
		if (twok[twok[x][k]][k] != -1) {
			twok[x][k+1] = twok[twok[x][k]][k];
		}
	}
	for (auto u : adj[x]) {
		if (u == par) continue;
		twok[u][0] = x;
		dfs(u, x);
	}
}
int sum(int a, int b) {
	if (twok[a][0] == -1) return pref[b];
	return pref[b]-pref[twok[a][0]];
}
void solve() {
	int n, q; cin >> n >> q;
	d[0] = 1e18; c[0] = 1e18;
	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);
	}
	memset(twok, -1, sizeof(twok));
	dfs(0, -1);
	int vis[MS];
	queue<int> qq;
	qq.push(0);
	pref[0] = 0;
	memset(vis, 0, sizeof(vis));
	vis[0] = 1;
	while (!qq.empty()) {
		int cur = qq.front();
		qq.pop();
		for (auto v : adj[cur]) {
			if (!vis[v]) {
				vis[v] = 1;
				qq.push(v);
				pref[v] = pref[cur]+c[v];
			}
		}
	}

	while (q--) {
		int r, v;
		cin >> r >> v;
		if (c[r] >= v) {
			cout << r << '\n'; continue; 
		}
		int original = r;
		for (int k = LOG-1; k >= 0; k--) {
			int temp = -1;
			if (r != -1) temp = twok[r][k]; 
			if (temp != -1 and sum(temp, original) < v) {
				r = temp;
			}
		}
		if (r == -1 or twok[r][0] == -1) cout << 0 << '\n';
		else cout << twok[r][0] << '\n';
	}
}
int32_t main() {
	int tc = 1;
	//cin >> tc;
	while (tc--) {solve();}
}

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