Submission #1021585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021585		mar	Fountain (eJOI20_fountain)	C++14	100 / 100	558 ms	53700 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100006;
const int loga = 30;

ll d[maxn],c[maxn][loga];
ll nxt[maxn][loga];


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()) {
            nxt[i+1][0] = st.top()+1;
        }
        st.push(i);
    }
    
    for(ll i=1; i<loga; i++) {
        for(ll j=1; j<=n; j++) {
            nxt[j][i] = nxt[nxt[j][i-1]][i-1];
            c[j][i] = c[j][i-1]+c[nxt[j][i-1]][i-1];    
        }
    }
    
    while(q--) {
        int ans, w; cin>>ans>>w;
        for(int i=loga-1; i>=0; i--) {
            if(w>c[ans][i]) {
                w-=c[ans][i];
                ans=nxt[ans][i];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

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