Submission #1312502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312502		bahaktl	Fountain (eJOI20_fountain)	C++20	100 / 100	259 ms	51708 KiB

fountain

#include <bits/stdc++.h>

#define int long long 
#define pb push_back
using namespace std;

const int N=2e5+10;
const int inf=9e18;
const int mod=1e9+7;

pair<int,int>a[N];

int up[N][30];
int sum[N][30];

signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    int T=1;
    // cin>>T;
    while(T--) {
        int n,q;
        cin>>n>>q;
        for(int i=0;i<=21;i++) {
            sum[n+1][i]=inf;
        }
        int d[n+1],c[n+1];
        d[0]=inf,c[0]=inf;
        for(int i=1;i<=n;i++) {
            cin>>d[i]>>c[i];
        }
        stack<int>st;
        st.push(0);
        for(int i=n;i>=1;i--) {
            while(d[i]>=d[st.top()]) {
                st.pop();

            }

            up[i][0]=st.top();
            sum[i][0]=c[st.top()];
            st.push(i);
        }
        for(int k=1;k<=21;k++) {
            for(int i=1;i<=n;i++) {
                up[i][k]=up[up[i][k-1]][k-1];
                sum[i][k]=sum[i][k-1]+sum[up[i][k-1]][k-1];
            }
        }
        while(q--) {
            int r,v;
            cin>>r>>v;
            if(v<=c[r]) {
                cout<<r<<"\n";
                continue;
            }
            v-=c[r];
            for(int i=21;i>=0;i--) {
                if(sum[r][i]<v) {
                    v-=sum[r][i];
                    r=up[r][i];
                }
            }
            cout<<up[r][0]<<"\n";
        }
    }
}

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