oj.uz

Submission #968967

# Submission time Handle Problem Language Result Execution time Memory
968967 2024-04-24T10:28:59 Z 0pt1mus23 Fountain (eJOI20_fountain) C++17
60 / 100
 537 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*1e5 +5,inf=1e9, prime = 2333;
/*
    * constraints?
    * segment tree / sparse table
    * odd / even
    * dp
    * dfs bfs
    * number theory, sieve
    * sorting
*/
const int L = 18;
int dp[L][sze];
int lg[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);
        }
    }

    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;
        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 3 ms 16732 KB Output is correct
2 Correct 6 ms 25268 KB Output is correct
3 Correct 5 ms 25176 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25944 KB Output is correct
7 Correct 5 ms 25180 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 54888 KB Output is correct
2 Correct 92 ms 53952 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 6 ms 25268 KB Output is correct
3 Correct 5 ms 25176 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25944 KB Output is correct
7 Correct 5 ms 25180 KB Output is correct
8 Correct 96 ms 54888 KB Output is correct
9 Correct 92 ms 53952 KB Output is correct
10 Correct 5 ms 25176 KB Output is correct
11 Runtime error 537 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -