Submission #1237790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237790		enzy	Fountain (eJOI20_fountain)	C++20	100 / 100	339 ms	38312 KiB

fountain

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10;
const int inf=1e9+7;
const int maxk=22;
int d[maxn], c[maxn], nxt[maxn][maxk], dp[maxn][maxk];
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, q; cin >> n >> q;
    for(int i=1;i<=n;i++) cin >> d[i] >> c[i];
    stack<int>st; st.push(0);
    c[0]=-1;
    d[0]=inf;
    for(int i=n;i>=1;i--){
        while(d[i]>=d[st.top()]) st.pop();
        nxt[i][0]=st.top();
        dp[i][0]=c[nxt[i][0]];
        st.push(i);
    }
    for(int k=1;k<maxk;k++)
        for(int i=0;i<=n;i++){
            nxt[i][k]=nxt[nxt[i][k-1]][k-1];
            dp[i][k]=dp[i][k-1]+dp[nxt[i][k-1]][k-1];
        }
    while(q--){
        int r, v; cin >> r >> v;
        v-=c[r];
        while(v>0&&r){
            int at=0;
            for(int k=0;k<maxk;k++) if(v-dp[r][k]>0) at=k;
            v-=dp[r][at]; 
            r=nxt[r][at];
        }
        cout << r << endl;
    }
}

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