oj.uz

Submission #909835

# Submission time Handle Problem Language Result Execution time Memory
909835 2024-01-17T13:07:35 Z pavement Fountain (eJOI20_fountain) C++17
100 / 100
 115 ms 22900 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 4 ms 15012 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 21448 KB Output is correct
2 Correct 89 ms 21488 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 4 ms 15012 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 79 ms 21448 KB Output is correct
9 Correct 89 ms 21488 KB Output is correct
10 Correct 3 ms 12888 KB Output is correct
11 Correct 46 ms 19540 KB Output is correct
12 Correct 115 ms 22900 KB Output is correct
13 Correct 96 ms 22280 KB Output is correct
14 Correct 98 ms 19500 KB Output is correct
15 Correct 74 ms 17644 KB Output is correct