Submission #969736

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

fountain

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
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=3*1e5 +5,inf=1e9, prime = 2333;
const int L = 17;
int dp[L+1][sze];
int qry(int l,int r){
    int i = log2(r-l +1);
    return max(dp[i][l],dp[i][r - (1<<i) +1]);
}
 
struct vv{
    int psum=0;
    int idx=0;
};
gp_hash_table<int,vec<vv>> blok;
gp_hash_table<int,vec<int>> graph;
struct{
    int deg;
    int p =-1;
    int leafid;
    int idxblok;
    int len;
    int val;
}  info[sze];
 
void dfs(int node,int parent=-1){
    info[node].p = parent;
    for(auto v:graph[node]){
        if(v!=parent){
            dfs(v,node);
        }
    }
}
 
void gkd(){
    int n,q;
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>info[i].len>>info[i].val;
        dp[0][i]=info[i].len;
        if(i+1>=2){
            // lg[i+1]=lg[(i+1)/2] +1;
        }
    }
    dp[0][n]=inf;
    // lg[n+1] = lg[(n+1)/2] +1;
    info[n].len=inf;
    info[n].val=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>info[i].len){
                ans=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        if(i!=ans){
            graph[i].pb(ans);
            graph[ans].pb(i);
            info[ans].deg++;
            info[i].deg++;
        }
    }
    dfs(n);
    int node;
    for(int i=0;i<n;i++){
        if(info[i].deg<=1){
            node = i;
            while(node!=-1){
                info[node].leafid  = i;
                info[node].idxblok = sz(blok[i]);
                blok[i].pb({0,node});
                node = info[node].p;
            }
            int sum=0;
            for(auto &v:blok[i]){
                // cout<<v.idx<<endl;
                v.psum = sum + info[v.idx].val;
                sum = v.psum; 
            }
        }
    }
    
    int water,mid,x,lf,ans,arxa,l,r;
    while(q--){
        cin>>node>>water;
        lf = info[node-1].leafid;
        ans=node-1;
        arxa = (info[node-1].idxblok? blok[lf][info[node-1].idxblok -1].psum : 0);
        l = info[node-1].idxblok+1;
        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){
            mid = (l+r)/2;
            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