oj.uz

Submission #866513

# Submission time Handle Problem Language Result Execution time Memory
866513 2023-10-26T09:39:49 Z hanifchdn Fountain (eJOI20_fountain) C++17
30 / 100
 188 ms 37936 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 37936 KB Output is correct
2 Correct 188 ms 36008 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -