Submission #909835

#	Time	Username	Problem	Language	Result	Execution time	Memory
909835		pavement	Fountain (eJOI20_fountain)	C++17	100 / 100	115 ms	22900 KiB

fountain

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

using ll = long long;

int N, Q, D[100005], wei[25][100005], anc[25][100005];
stack<int> S;

int main() {
	memset(anc, -1, sizeof anc);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		cin >> D[i] >> wei[0][i];
	}
	for (int i = N; i >= 1; i--) {
		while (!S.empty() && D[S.top()] <= D[i]) {
			S.pop();
		}
		anc[0][i] = (S.empty() ? N + 1 : S.top());
		S.push(i);
	}
	for (int k = 1; k <= 20; k++) {
		for (int i = 1; i <= N; i++) {
			if (anc[k - 1][i] == -1) {
				continue;
			}
			anc[k][i] = anc[k - 1][anc[k - 1][i]];
			wei[k][i] = wei[k - 1][i] + wei[k - 1][anc[k - 1][i]];
		}
	}
	for (int i = 1, R, V; i <= Q; i++) {
		cin >> R >> V;
		for (int k = 20; k >= 0; k--) {
			if (anc[k][R] == -1) {
				continue;
			}
			if (wei[k][R] < V) {
				V -= wei[k][R];
				R = anc[k][R];
			}
		}
		cout << (R == N + 1 ? 0 : R) << '\n';
	}
}

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