Submission #754668

#	Time	Username	Problem	Language	Result	Execution time	Memory
754668		mraron	Fountain (eJOI20_fountain)	C++14	100 / 100	735 ms	38856 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
#define xx first 
#define yy second 
using ll = long long ;
int main() {
    int n,q;
    cin>>n>>q;
    vector<pair<int,int>> t(n);
    for(int i=0;i<n;++i) {
        cin>>t[i].xx>>t[i].yy;
    }
    
    t.push_back({1e9+1, 1e9+1});
    
    vector<int> nxt(n+1);
    nxt[n]=n;
    
    vector<int> st={n};
    for(int i=n-1;i>=0;i--) {
        while(!st.empty() && t[st.back()].xx<=t[i].xx) st.pop_back();
        nxt[i]=st.back();
        st.push_back(i);
    }
    
    vector<array<ll,20>> dp(n+1), ends(n+1);
    for(int i=0;i<=n;++i) {
        dp[i][0]=t[i].yy;
        ends[i][0]=i;
    }
    for(int j=1;j<20;++j) {
        for(int i=0;i<=n;++i) {
            dp[i][j]=dp[i][j-1]+dp[nxt[ends[i][j-1]]][j-1];
            ends[i][j]=ends[nxt[ends[i][j-1]]][j-1];
        }
    }
    

    for(int i=0;i<q;++i) {
        int ind;
        ll c;
        cin>>ind>>c;
        ind--;
        for(int j=19;j>=0;j--) {
            if(dp[ind][j]<=c) {
                c-=dp[ind][j];
                ind=(c?nxt[ends[ind][j]]:ends[ind][j]);
            }
        }
        
        cout<<(ind==n?0:ind+1)<<"\n";
    }
}

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