oj.uz

Submission #681856

# Submission time Handle Problem Language Result Execution time Memory
681856 2023-01-14T17:37:54 Z peijar Fountain (eJOI20_fountain) C++17
100 / 100
 261 ms 21248 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 0 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 468 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 1 ms 540 KB Output is correct
7 Correct 1 ms 472 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 18888 KB Output is correct
2 Correct 180 ms 17964 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 468 KB Output is correct
5 Correct 2 ms 484 KB Output is correct
6 Correct 1 ms 540 KB Output is correct
7 Correct 1 ms 472 KB Output is correct
8 Correct 213 ms 18888 KB Output is correct
9 Correct 180 ms 17964 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 73 ms 11292 KB Output is correct
12 Correct 261 ms 21200 KB Output is correct
13 Correct 181 ms 20888 KB Output is correct
14 Correct 148 ms 20052 KB Output is correct
15 Correct 132 ms 21248 KB Output is correct