oj.uz

Submission #866514

# Submission time Handle Problem Language Result Execution time Memory
866514 2023-10-26T09:40:56 Z hanifchdn Fountain (eJOI20_fountain) C++17
100 / 100
 235 ms 40016 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 1e5 + 5;

ll d[N], a[N];
pair<int, ll> par[N][20];
stack<pair<int, ll>> s;

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> d[i] >> a[i];
    a[0] = 2e9;
    s.push({0, 2e9});
    for (int i = n; i >= 1; i--) {
        while (d[i] >= s.top().se) s.pop();
        par[i][0] = {s.top().fi, a[s.top().fi]};
        for (int j = 1; j < 20; j++) par[i][j] = {par[par[i][j - 1].fi][j - 1].fi, par[par[i][j - 1].fi][j - 1].se + par[i][j - 1].se};
        s.push({i, d[i]});
    }
    while (q--) {
        int r;
        ll v;
        cin >> r >> v;
        v -= a[r];
        if (v <= 0) {
            cout << r << "\n";
            continue;
        }
        for (int i = 19; i >= 0; i--) {
            if (par[r][i].se < v) {
                v -= par[r][i].se;
                r = par[r][i].fi;
            }
        }
        cout << par[r][0].fi << "\n";
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 2524 KB Output is correct
4 Correct 1 ms 2520 KB Output is correct
5 Correct 1 ms 2772 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 35164 KB Output is correct
2 Correct 158 ms 32944 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 2524 KB Output is correct
4 Correct 1 ms 2520 KB Output is correct
5 Correct 1 ms 2772 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 186 ms 35164 KB Output is correct
9 Correct 158 ms 32944 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 58 ms 22356 KB Output is correct
12 Correct 235 ms 40016 KB Output is correct
13 Correct 122 ms 38284 KB Output is correct
14 Correct 98 ms 37300 KB Output is correct
15 Correct 74 ms 37496 KB Output is correct