oj.uz

Submission #576271

# Submission time Handle Problem Language Result Execution time Memory
576271 2022-06-12T21:10:52 Z mars Fountain (eJOI20_fountain) C++14
100 / 100
 288 ms 21228 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int dp[100005][20];
int water[100005][20];

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 <= 19; 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 = 19; 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 18776 KB Output is correct
2 Correct 242 ms 17920 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 196 ms 18776 KB Output is correct
9 Correct 242 ms 17920 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 77 ms 11532 KB Output is correct
12 Correct 288 ms 21188 KB Output is correct
13 Correct 190 ms 20836 KB Output is correct
14 Correct 139 ms 20012 KB Output is correct
15 Correct 129 ms 21228 KB Output is correct