oj.uz

Submission #697356

# Submission time Handle Problem Language Result Execution time Memory
697356 2023-02-09T12:30:32 Z nasir_bashirov Fountain (eJOI20_fountain) C++11
100 / 100
 666 ms 17944 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 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 5 ms 656 KB Output is correct
7 Correct 6 ms 724 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 16112 KB Output is correct
2 Correct 474 ms 15068 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 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 5 ms 656 KB Output is correct
7 Correct 6 ms 724 KB Output is correct
8 Correct 402 ms 16112 KB Output is correct
9 Correct 474 ms 15068 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 227 ms 9720 KB Output is correct
12 Correct 666 ms 17140 KB Output is correct
13 Correct 523 ms 17188 KB Output is correct
14 Correct 451 ms 17228 KB Output is correct
15 Correct 470 ms 17944 KB Output is correct