oj.uz

Submission #969736

# Submission time Handle Problem Language Result Execution time Memory
969736 2024-04-25T14:11:16 Z 0pt1mus23 Fountain (eJOI20_fountain) C++14
60 / 100
 646 ms 524288 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21592 KB Output is correct
2 Correct 6 ms 34140 KB Output is correct
3 Correct 7 ms 34392 KB Output is correct
4 Correct 6 ms 34396 KB Output is correct
5 Correct 7 ms 34328 KB Output is correct
6 Correct 7 ms 35932 KB Output is correct
7 Correct 5 ms 34396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 81916 KB Output is correct
2 Correct 136 ms 81484 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 21592 KB Output is correct
2 Correct 6 ms 34140 KB Output is correct
3 Correct 7 ms 34392 KB Output is correct
4 Correct 6 ms 34396 KB Output is correct
5 Correct 7 ms 34328 KB Output is correct
6 Correct 7 ms 35932 KB Output is correct
7 Correct 5 ms 34396 KB Output is correct
8 Correct 144 ms 81916 KB Output is correct
9 Correct 136 ms 81484 KB Output is correct
10 Correct 5 ms 34396 KB Output is correct
11 Runtime error 646 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -