oj.uz

Submission #465511

# Submission time Handle Problem Language Result Execution time Memory
465511 2021-08-16T09:06:23 Z Sench2006 Fountain (eJOI20_fountain) C++14
100 / 100
 331 ms 25696 KB 
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;

#define ll long long
#define ar array

#define f first
#define s second
#define mpr make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound

#define FOR(i, a, b) for(auto i = a; i < b; i++)
#define FORD(i, a, b) for(auto i = a - 1; i >= b; i--)
#define trav(x, v) for(auto x : v)

#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fileio freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

// --------------- SOLUTION --------------- //

const int mxN = 1e5+5;
int n, q;
pair <int, int> in[mxN];
pair <int, int> ch[mxN][25];
vector <pair<int, int>> st;

void solve() {
    cin >> n >> q;
    FOR(i, 1, n + 1) {
        cin >> in[i].f >> in[i].s;
    }
    FORD(i, n + 1, 1) {
        while (!st.empty() && st.back().f <= in[i].f) st.pop_back();
        if (st.empty()) ch[i][0] = {0, in[i].s};
        else ch[i][0] = {st.back().s, in[i].s};
        st.pb({in[i].f, i});
    }
    FOR(j, 1, 20) {
        FOR(i, 1, n + 1) {
            ch[i][j] = {ch[ch[i][j - 1].f][j - 1].f, ch[i][j - 1].s + ch[ch[i][j - 1].f][j - 1].s};
        }
    }
    while (q--) {
        int r, v;
        cin >> r >> v;
        FORD(i, 20, 0) {
            if (v > ch[r][i].s) {
                v -= ch[r][i].s;
                r = ch[r][i].f;
            }
        }
        cout << r << "\n";
    }
}

int main() {
    fastio;
    // fileio;
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 23036 KB Output is correct
2 Correct 246 ms 22196 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 217 ms 23036 KB Output is correct
9 Correct 246 ms 22196 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 91 ms 14040 KB Output is correct
12 Correct 331 ms 25696 KB Output is correct
13 Correct 258 ms 25160 KB Output is correct
14 Correct 159 ms 24672 KB Output is correct
15 Correct 150 ms 24676 KB Output is correct