oj.uz

Submission #441457

# Submission time Handle Problem Language Result Execution time Memory
441457 2021-07-05T08:23:10 Z elazarkoren Fountain (eJOI20_fountain) C++17
100 / 100
 845 ms 34616 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#define x first
#define y second
#define int long long
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 1e5 + 2;
const int infinity = 1e9 + 1;

int d[MAX_N], c[MAX_N], loga[MAX_N];

int32_t main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> d[i] >> c[i];
    for (int i = 2; i <= n; i++) {
        loga[i] = loga[i >> 1] + 1;
    }
    vector<vii> dp(loga[n] + 1, vii(n + 2, {n + 1, infinity}));
    d[n + 1] = c[n + 1] = infinity;
    stack<int> stk;
    stk.push(n + 1);
    for (int i = n; i; i--) {
        while (d[stk.top()] <= d[i]) stk.pop();
        dp[0][i] = {stk.top(), c[i]};
        stk.push(i);
    }
    for (int i = 1; i <= loga[n]; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j].x = dp[i - 1][dp[i - 1][j].x].x;
            dp[i][j].y = dp[i - 1][j].y + dp[i - 1][dp[i - 1][j].x].y;
        }
    }
    while (q--) {
        int r, v;
        cin >> r >> v;
        for (int i = loga[n]; i >= 0; i--) {
            if (dp[i][r].y < v) {
                v -= dp[i][r].y;
                r = dp[i][r].x;
            }
        }
        cout << (r == n + 1 ? 0 : r) << '\n';
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 304 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 6 ms 540 KB Output is correct
6 Correct 6 ms 440 KB Output is correct
7 Correct 5 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 29364 KB Output is correct
2 Correct 606 ms 27916 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 304 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 5 ms 460 KB Output is correct
5 Correct 6 ms 540 KB Output is correct
6 Correct 6 ms 440 KB Output is correct
7 Correct 5 ms 460 KB Output is correct
8 Correct 533 ms 29364 KB Output is correct
9 Correct 606 ms 27916 KB Output is correct
10 Correct 6 ms 460 KB Output is correct
11 Correct 324 ms 17824 KB Output is correct
12 Correct 845 ms 34616 KB Output is correct
13 Correct 744 ms 33824 KB Output is correct
14 Correct 600 ms 33308 KB Output is correct
15 Correct 603 ms 33640 KB Output is correct