oj.uz

Submission #969423

# Submission time Handle Problem Language Result Execution time Memory
969423 2024-04-25T06:43:32 Z 0pt1mus23 Fountain (eJOI20_fountain) C++14
60 / 100
 426 ms 524288 KB 
#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*1e6 +5,inf=1e9, prime = 2333;
const int L = 18;
int dp[L+10][sze+100];
int lg[sze+100];
 
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+100];
 
struct vv{
    int psum=0;
    int idx=0;
};
vec<vv> blok[sze+100];
vec<int> tree[sze+100];
struct{
    int deg=0;
    int p =-1;
    int leafid=0;
    int idxblok = 0;
} info[sze+100];
 
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+100];
    int val[n+100];
    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);
        }
    }
 
    vec<vv> lst;
    for(auto leaf:leafs){
        lst.clear();
        int node = leaf;
        while(node!=-1){
            info[node].leafid  = leaf;
            info[node].idxblok = sz(lst);
            lst.pb({0,node});
            node = info[node].p;
        }
        blok[leaf]=lst;
    }
    // -- debug --
    // for(int i=0;i<n+1;i++){
    //     cout<<"-- start : "<<i<<" --"<<endl;
    //     for(auto v:blok[i]){
    //         cout<<v.idx<<" info ? " << info[v.idx].idxblok <<" "<< info[v.idx].idxblok <<endl;
    //     }
    // }
 
    for(int i=0;i<=n;i++){
        int sum=0;
        blok[i].pb({0,0});
        for(auto &v:blok[i]){
            // 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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 104016 KB Output is correct
2 Correct 27 ms 116568 KB Output is correct
3 Correct 25 ms 116560 KB Output is correct
4 Correct 25 ms 116824 KB Output is correct
5 Correct 25 ms 116532 KB Output is correct
6 Correct 26 ms 118360 KB Output is correct
7 Correct 26 ms 116816 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 164152 KB Output is correct
2 Correct 116 ms 163264 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 104016 KB Output is correct
2 Correct 27 ms 116568 KB Output is correct
3 Correct 25 ms 116560 KB Output is correct
4 Correct 25 ms 116824 KB Output is correct
5 Correct 25 ms 116532 KB Output is correct
6 Correct 26 ms 118360 KB Output is correct
7 Correct 26 ms 116816 KB Output is correct
8 Correct 117 ms 164152 KB Output is correct
9 Correct 116 ms 163264 KB Output is correct
10 Correct 26 ms 117136 KB Output is correct
11 Runtime error 426 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -