oj.uz

Submission #697355

# Submission time Handle Problem Language Result Execution time Memory
697355 2023-02-09T12:29:54 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 630 ms 21152 KB 
#include<bits/stdc++.h>
using namespace std;

int st[20][100005], water[25][100005], dia;

int main(){
    int n, q;
    cin >> n >> q;
    stack<pair<int, int>> mst;
    for(int i = 1; i <= n; i++){
        cin >> dia >> water[0][i];
        while(!mst.empty() and dia > mst.top().first){
            st[0][mst.top().second] = i;
            mst.pop();
        }
        mst.push({dia, i});
    }

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

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

    while(q--){
        int s, w;
        cin >> s >> w;
        for(int i = 19; i >= 0; i--){
            if(water[i][s] >= w)    continue;
            w -= water[i][s];
            s = st[i][s];
        }
        cout << s << endl;
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 5 ms 576 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 19060 KB Output is correct
2 Correct 509 ms 18076 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 6 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 5 ms 576 KB Output is correct
8 Correct 420 ms 19060 KB Output is correct
9 Correct 509 ms 18076 KB Output is correct
10 Correct 5 ms 596 KB Output is correct
11 Correct 250 ms 11444 KB Output is correct
12 Correct 630 ms 21152 KB Output is correct
13 Correct 555 ms 20812 KB Output is correct
14 Correct 448 ms 20060 KB Output is correct
15 Correct 435 ms 21152 KB Output is correct