oj.uz

Submission #1007518

# Submission time Handle Problem Language Result Execution time Memory
1007518 2024-06-25T05:45:47 Z spensa Fountain (eJOI20_fountain) C++17
0 / 100
 61 ms 23980 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Incorrect 2 ms 18780 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 61 ms 23980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Incorrect 2 ms 18780 KB Output isn't correct
3 Halted 0 ms 0 KB -