oj.uz

Submission #632914

# Submission time Handle Problem Language Result Execution time Memory
632914 2022-08-21T08:18:14 Z nasir_bashirov Fountain (eJOI20_fountain) C++11
100 / 100
 273 ms 21272 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 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 476 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 192 ms 18820 KB Output is correct
2 Correct 211 ms 17888 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 2 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 476 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 192 ms 18820 KB Output is correct
9 Correct 211 ms 17888 KB Output is correct
10 Correct 1 ms 472 KB Output is correct
11 Correct 77 ms 11376 KB Output is correct
12 Correct 273 ms 21068 KB Output is correct
13 Correct 170 ms 20876 KB Output is correct
14 Correct 142 ms 20044 KB Output is correct
15 Correct 120 ms 21272 KB Output is correct