Submission #1123072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123072		ezzzay	Fountain (eJOI20_fountain)	C++20	100 / 100	469 ms	28012 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int a[N];
bool vis[N];
int d[N],c[N];
vector<int>ans ;
vector<int>v[N];
int par[30][N];
int dst[N];
void dfs(int a){
    dst[a]+=c[a];
    for(auto b:v[a]){
        dst[b]+=dst[a];
        dfs(b);
    }
}
signed main(){
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>d[i]>>c[i];
    }
    c[n+1]=1e9;
    stack<pair<int,int>> st;
    st.push({int(1e9), int(n+1)}) ;
    for(int i=n;i>=1;i--){
        while (!st.empty() && st.top().first <= d[i]) st.pop();
        int p=st.top().ss;
        v[p].pb(i);
        par[0][i]=p;
		st.push({d[i], i});
    }
    par[0][n+1]=n+1;
    for(int i=1;i<22;i++){
        for(int j=1;j<=n;j++){
            par[i][j]=par[i-1][par[i-1][j]];
        }
    }
    dfs(n+1);
    while(q--){
        int x,v;
        cin>>x>>v;
        for(int i=20;i>=0;i--){
            int p=par[i][x];
            if(dst[x]-dst[p]<v){
                v-=dst[x]-dst[p];
                x=p;
            }
        }
        if(x==n+1)x=0;
        ans.pb(x);
    }
    for(auto a:ans)cout<<a<<endl;
}

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