Submission #1125123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125123		Pwo	Fountain (eJOI20_fountain)	C++20	100 / 100	253 ms	31352 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, q;
pair<int, int> a[100005];
vector<int> g[100005];
int pre[100005],up[100005][20];

void dfs(int v) {
	for (const int u : g[v]) {
		pre[u] = pre[v] + a[u].second;
		up[u][0] = v;
		for (int i = 1; i < 17; i++)
			up[u][i] = up[up[u][i - 1]][i - 1];
		dfs(u);
	}
}

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
	vector<int> v;
	for (int i = 1; i <= n; i++) {
		while (!v.empty() && a[v.back()].first < a[i].first) {
			g[i].push_back(v.back());
			v.pop_back();
		}
		v.push_back(i);
	}
	for (const int u : v) g[0].push_back(u);
	dfs(0);
	
	while (q--) {
		int r, v; cin >> r >> v; v--;
		int cur = r;
		for (int i = 16; i >= 0; i--)
			if (pre[r] - pre[up[cur][i]] <= v)
				cur = up[cur][i];
		cout << cur << '\n';
	}
}

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