Submission #968986

#	Time	Username	Problem	Language	Result	Execution time	Memory
968986		0pt1mus23	Fountain (eJOI20_fountain)	C++14	60 / 100	529 ms	524288 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define sz(arr) arr.size()
#define ins insert
#define pb push_back
#define str string
#define pii pair<int,int>
#define int long long int
#define endl "\n"
#define vec vector
#define drop(x) cout<<x<<endl;return
const int mod = 1e9 +7 , sze=2*1e5 +5,inf=1e9, prime = 2333;
const int L = 18;
int dp[L+5][sze];
int lg[sze];
int len[sze];
int val[sze];
int qry(int l,int r){
    int i = lg[r-l +1];
    return max(dp[i][l],dp[i][r - (1<<i) +1]);
}

int dspar[sze];

struct vv{
    int psum=0;
    int idx=0;
};
vec<vv> blok[sze];
vec<int> tree[sze];
struct{
    int deg=0;
    int p =-1;
    int leafid=0;
    int idxblok = 0;
} info[sze];

void dfs(int node,int parent=-1){
    info[node].p = parent;
    for(auto v:tree[node]){
        if(v!=parent){
            dfs(v,node);
        }
    }
}

void gkd(){
    int n,q;
    cin>>n>>q;
    int len[n+3];
    int val[n+3];
    vec<int> leafs;
    len[0]=0,val[0]=0;
    for(int i=0;i<n;i++){
        cin>>len[i]>>val[i];
        dp[0][i]=len[i];
        if(i+1>=2){
            lg[i+1]=lg[(i+1)/2] +1;
        }
        dspar[i]=i;
    }
    dp[0][n]=inf;
    lg[n+1] = lg[(n+1)/2] +1;
    len[n]=inf;
    val[n]=inf;
    for(int i=1;i<=L;i++){
        for(int j=0;j + (1<<i)<=n+1;j++){
            dp[i][j] = max(dp[i-1][j],dp[i-1][j + (1<<(i-1))]);
        }
    }
    for(int i=n;i>=0;i--){
        int l = i;
        int r = n;
        int ans = i;
        while(l<=r){
            int mid = (l+r)/2;
            int qq = qry(i,mid);
            if(qq>len[i]){
                ans=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        if(i!=ans){
            tree[i].pb(ans);

            tree[ans].pb(i);
            info[ans].deg++;
            
            info[i].deg++;
            dspar[i]=dspar[ans];
        }
    }
    dfs(n);
    for(int i=0;i<n;i++){
        if(info[i].deg<=1){
            leafs.pb(i);
        }
    }

    for(auto leaf:leafs){
        int node = leaf;
        while(node!=-1){
            info[node].leafid  = leaf;
            info[node].idxblok = sz(blok[leaf]);
            blok[leaf].pb({0,node});
            node = info[node].p;
        }
        int sum=0;
        for(auto &v:blok[leaf]){
            // cout<<v.idx<<endl;
            v.psum = sum + val[v.idx];
            sum = v.psum; 
        }
    }
    

    while(q--){
        int node,water;
        cin>>node>>water;
        int lf = info[node-1].leafid;
        int ans=node-1;
        int arxa = (info[node-1].idxblok? blok[lf][info[node-1].idxblok -1].psum : 0);
        int l = info[node-1].idxblok+1;
        int r = sz( blok[lf])-1;
        // cout<<lf<<endl;
        // for(auto v:blok[lf]){
        //     cout<<v.psum<<" :: "<<v.idx<<endl;
        // }
        // cout<<l<<" "<<r<<endl;

        while(l<=r){
            int mid = (l+r)/2;
            int x = ( mid?blok[lf][mid-1].psum : 0 )  - arxa;

            if(water - x >=1){
                ans=blok[lf][mid].idx;
                // cout<<x<<" olur "<<endl;
                l=mid+1;
            } 
            else{
                r=mid-1;
            }
        }

        if(ans+1==n+1){
            cout<<0<<endl;
        }
        else{
            cout<<ans+1<<endl;
        }
    }
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int tt=1; 
    // cin>>tt;
    while(tt--) gkd();
    return 0;
}

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