oj.uz

Submission #366300

# Submission time Handle Problem Language Result Execution time Memory
366300 2021-02-13T20:14:44 Z model_code Fountain (eJOI20_fountain) C++17
100 / 100
 318 ms 18152 KB 
// https://ideone.com/BYIOiA

#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 384 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 16060 KB Output is correct
2 Correct 224 ms 14948 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 201 ms 16060 KB Output is correct
9 Correct 224 ms 14948 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 95 ms 9708 KB Output is correct
12 Correct 318 ms 17260 KB Output is correct
13 Correct 248 ms 17456 KB Output is correct
14 Correct 173 ms 17216 KB Output is correct
15 Correct 147 ms 18152 KB Output is correct