Submission #697356

#	Time	Username	Problem	Language	Result	Execution time	Memory
697356		nasir_bashirov	Fountain (eJOI20_fountain)	C++11	100 / 100	666 ms	17944 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40