Submission #1007518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007518		spensa	Fountain (eJOI20_fountain)	C++17	0 / 100	61 ms	23980 KiB

fountain

#include <iostream>
#include <vector>
#include <set>
#include <stack>
#include <utility>
#include <cmath>
using namespace std;
typedef long long ll;

const int MXN = 1e5 + 10 ;
int cap[MXN] = {0};
int di[MXN] = {0};
int pscap[MXN] = {0};
vector<int> G[MXN];
pair<int, int> successor[20][MXN];
const int INF = 1e8 + 300;

int main(){
    //faster io
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    cin>>N>>Q;

    for(int i=1; i<=N; i++) cin>>di[i]>>cap[i];

    //themselves
    for(int i=1; i<N; i++){
        successor[0][i].first = i;
        successor[0][i].second = cap[i];
    }

    //N + 1 nodes
    stack<pair<int, int>> st;
    for(int i=N; i>=1; i--){
        if(st.empty()){
            G[i].push_back(N+1);
            successor[1][i].first = N+1;
            successor[1][i].second = INF;
            st.push(make_pair(di[i], i));
            continue;
        }
        while((!st.empty()) && ((st.top().first)<di[i])){
            st.pop();
        }
        if(st.empty()){
            G[i].push_back(N+1);
            successor[1][i].first = N+1;
            successor[1][i].second = INF;
        }
        else{
            G[i].push_back(st.top().second);
            successor[1][i].first = st.top().second;
            successor[1][i].second = cap[st.top().second] + cap[i];
        }
        st.push(make_pair(di[i], i));
    }

    // cout<<"hi";
    // for(int i=1; i<=N; i++){
    //     cout<<successor[1][i].first<<" "<<successor[1][i].second<<"\n";
    // }


    //binary jumping matrix for successors
    for(int i=2; i<20; i++){
        for(int j=1; j<=N; j++){
            successor[i][j].first = successor[i-1][successor[i-1][j].first].first;
            if((successor[i-1][successor[i-1][j].first].second==INF) ||
                (successor[i-1][j].second==INF)){
                    successor[i][j].second = INF;
                    continue;
            }
            successor[i][j].second = successor[i-1][j].second + successor[i-1][successor[i-1][j].first].second;
            successor[i][j].second -= cap[successor[i-1][j].first];
        }
    }

    // for(int j=1; j<20; j++){
    //     cout<<"j="<<j<<"\n";
    //     cout<<successor[j][1].first<<" "<<successor[j][1].second<<"\n";
    // }
    // cout<<"\n";
    // for(int j=1; j<20; j++){
    //     cout<<"j="<<j<<"\n";
    //     cout<<successor[j][2].first<<" "<<successor[j][2].second<<"\n";
    // }

    while(Q--){
        int R, V;
        cin>>R>>V;

        if(V<=cap[R]){
            cout<<R<<"\n";
            continue;
        }

        int a = R;
        //binary search amongst R's successors
        for(int i=19; i>=1; i--){
            // cout<<a<<" ";
            if(successor[i][a].second>V){
                continue;
            }
            if(successor[i][a].second<V){
                // cout<<"hi";
                a = successor[i][a].first;
            }
        }
        a = successor[1][a].first;
        // cout<<"\n";
        if(a==(N+1)) cout<<"0\n";
        else cout<<a<<"\n";

    }
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40