oj.uz

Submission #1007546

# Submission time Handle Problem Language Result Execution time Memory
1007546 2024-06-25T07:10:40 Z spensa Fountain (eJOI20_fountain) C++17
100 / 100
 105 ms 28696 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";
                V-=successor[i][a].second;
                a = successor[i][a].first;
                V+=cap[a];
                // cout<<"V="<<V<<" ";
            }
        }
        // cout<<a<<" ";
        a = successor[1][a].first;
        // cout<<a<<"\n";
        if(a==(N+1)) cout<<"0\n";
        else cout<<a<<"\n";

    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 23944 KB Output is correct
2 Correct 64 ms 23604 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18916 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct
8 Correct 61 ms 23944 KB Output is correct
9 Correct 64 ms 23604 KB Output is correct
10 Correct 2 ms 18780 KB Output is correct
11 Correct 39 ms 23240 KB Output is correct
12 Correct 105 ms 28696 KB Output is correct
13 Correct 86 ms 27472 KB Output is correct
14 Correct 54 ms 26760 KB Output is correct
15 Correct 45 ms 26956 KB Output is correct