Submission #1048649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048649		mar	Fountain (eJOI20_fountain)	C++14	100 / 100	442 ms	33404 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100007;
const int logi=17;
 
ll d[maxn],c[maxn][logi];
ll up[maxn][logi];

int main() {
    int n,q; cin>>n>>q;
    for(int i=0; i <n; i++) {
        cin>>d[i]>>c[i+1][0];
    }
    stack<int>st;
    for(int i=n-1; i>=0; i--) {
        while(!st.empty() && d[st.top()] <= d[i]) st.pop();
        if(!st.empty()) up[i+1][0] = st.top()+1;
        st.push(i);
    }
    for(int i=1; i<logi; i++) {
        for(int j=1; j<=n; j++) {
            up[j][i] = up[up[j][i-1]][i-1];
            c[j][i] = c[j][i-1]+c[up[j][i-1]][i-1];    
        }
    }
    while(q--) {
        int ans, w; cin>>ans>>w;
        for(int i=logi-1; i>=0; i--) {
            if(w>c[ans][i]) {
                w-=c[ans][i];
                ans=up[ans][i];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

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