oj.uz

Submission #459472

# Submission time Handle Problem Language Result Execution time Memory
459472 2021-08-08T14:12:11 Z liza Fountain (eJOI20_fountain) C++14
100 / 100
 292 ms 20452 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int MAX = 19;
int dp[100005][MAX];
int water[100005][MAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q, diam, a, b;
    cin >> n >> q;
    priority_queue<pair<int, int>> pq; // diameter, id

    for (int i = 1; i <= n; i++) {
        cin >> diam >> water[i][0];
        while(!pq.empty() && -pq.top().first < diam) {
            dp[pq.top().second][0] = i;
            pq.pop();
        }
        pq.push({-diam, i});
    }

    while(!pq.empty()) {
        dp[pq.top().second][0] = 0;
        pq.pop();
    }

    dp[0][0] = 0;
    water[0][0] = 0;

    for (int j = 1; j <= MAX - 1; j++) {
        for (int i = 0; i <= n; i++) {
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
            water[i][j] = water[i][j - 1] + water[dp[i][j - 1]][j - 1];
        }
    }

    while(q--) {
        cin >> a >> b;
        for (int j = MAX - 1; j >= 0; j--) {
            if (water[a][j] >= b) {continue;}
            b -= water[a][j];
            a = dp[a][j];
        }

        cout << a << "\n";
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 460 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 196 ms 16468 KB Output is correct
2 Correct 215 ms 17236 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 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 196 ms 16468 KB Output is correct
9 Correct 215 ms 17236 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 86 ms 10832 KB Output is correct
12 Correct 292 ms 20300 KB Output is correct
13 Correct 226 ms 20124 KB Output is correct
14 Correct 184 ms 19184 KB Output is correct
15 Correct 150 ms 20452 KB Output is correct