oj.uz

Submission #832363

# Submission time Handle Problem Language Result Execution time Memory
832363 2023-08-21T09:42:53 Z Pekiban Fountain (eJOI20_fountain) C++17
60 / 100
 131 ms 31236 KB 
#include <bits/stdc++.h>

using namespace std;

const int mxN = 1e5+1, LOG = 20;
vector<int> adj[mxN];
pair<int, int> up[LOG][mxN];
int 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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18260 KB Output is correct
2 Correct 9 ms 18340 KB Output is correct
3 Correct 9 ms 18388 KB Output is correct
4 Correct 9 ms 18388 KB Output is correct
5 Correct 9 ms 18460 KB Output is correct
6 Correct 9 ms 18348 KB Output is correct
7 Correct 9 ms 18352 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 29936 KB Output is correct
2 Correct 131 ms 29620 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18260 KB Output is correct
2 Correct 9 ms 18340 KB Output is correct
3 Correct 9 ms 18388 KB Output is correct
4 Correct 9 ms 18388 KB Output is correct
5 Correct 9 ms 18460 KB Output is correct
6 Correct 9 ms 18348 KB Output is correct
7 Correct 9 ms 18352 KB Output is correct
8 Correct 109 ms 29936 KB Output is correct
9 Correct 131 ms 29620 KB Output is correct
10 Correct 10 ms 18388 KB Output is correct
11 Correct 58 ms 23240 KB Output is correct
12 Incorrect 91 ms 31236 KB Output isn't correct
13 Halted 0 ms 0 KB -