oj.uz

답안 #832368

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
832368 2023-08-21T09:44:55 Z Pekiban Fountain (eJOI20_fountain) C++17
100 / 100
 343 ms 48032 KB 
#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) {
        while (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';
    }
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 33876 KB Output is correct
2 Correct 15 ms 34004 KB Output is correct
3 Correct 15 ms 34024 KB Output is correct
4 Correct 15 ms 34004 KB Output is correct
5 Correct 16 ms 34004 KB Output is correct
6 Correct 16 ms 34004 KB Output is correct
7 Correct 19 ms 34128 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 46260 KB Output is correct
2 Correct 214 ms 45948 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 33876 KB Output is correct
2 Correct 15 ms 34004 KB Output is correct
3 Correct 15 ms 34024 KB Output is correct
4 Correct 15 ms 34004 KB Output is correct
5 Correct 16 ms 34004 KB Output is correct
6 Correct 16 ms 34004 KB Output is correct
7 Correct 19 ms 34128 KB Output is correct
8 Correct 188 ms 46260 KB Output is correct
9 Correct 214 ms 45948 KB Output is correct
10 Correct 15 ms 34004 KB Output is correct
11 Correct 84 ms 39496 KB Output is correct
12 Correct 343 ms 48032 KB Output is correct
13 Correct 219 ms 44440 KB Output is correct
14 Correct 160 ms 43168 KB Output is correct
15 Correct 140 ms 43884 KB Output is correct