| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 832367 | Pekiban | Fountain (eJOI20_fountain) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5+1, LOG = 20;
vector<int> adj[mxN];
pair<int, long long> up[LOG][mxN];
long long d[mxN], c[mxN];
void dfs(int s, int e) {
for (auto u : adj[s]) {
if (u == e) continue;
up[0][u] = {s, c[s]};
dfs(u, s);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
d[0] = 1e9+1, c[0] = 1e9+1;
for (int i = 0; i < LOG; ++i) {
for (int j = 0; j < mxN; ++j) {
up[i][j] = {-1, -1};
}
}
up[0][0] = {-1, 0};
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
cin >> d[i] >> c[i];
}
stack<pair<int, int>> s; s.push({1e9+1, 0}); s.push({d[n], n}); adj[n].push_back(0); adj[0].push_back(n);
int f[n+1]; f[n] = 0;
for (int i = n-1; i >= 1; --i) {
whijavascript:tab_clicked(1)le (s.top().first <= d[i]) {
s.pop();
}
f[i] = s.top().second;
s.push({d[i], i});
adj[i].push_back({f[i]}), adj[f[i]].push_back({i});
}
dfs(0, -1);
for (int i = 1; i < LOG; ++i) {
for (int j = 1; j <= n; ++j) {
up[i][j] = {up[i-1][up[i-1][j].first].first, up[i-1][up[i-1][j].first].second + up[i-1][j].second};
}
}
while (q--) {
int r, v;
cin >> r >> v;
v -= c[r];
for (int i = LOG-1; i >= 0; --i) {
if (up[i][r].second <= v) {
v -= up[i][r].second;
r = up[i][r].first;
}
}
cout << (v > 0 ? up[0][r].first : r) << '\n';
}
}