Submission #396832

#	Time	Username	Problem	Language	Result	Execution time	Memory
396832		Pichon5	Fountain (eJOI20_fountain)	C++17	30 / 100	66 ms	10636 KiB

fountain

#include <iostream>
#include <bits/stdc++.h>
#define vi vector<int>
#define pb push_back
#define F first
#define S second
#define ll long long
#define vll vector<ll>
using namespace std;
const int tam=1e5+5;
int T[tam];
vll v;
void init(int nodo,int b, int e){
    int L=2*nodo+1,R=L+1,mid=(b+e)/2;
    if(b==e){
        T[nodo]=v[b];
        return;
    }
    init(L,b,mid);init(R,mid+1,e);
    T[nodo]=max(T[L],T[R]);
}
int query(int nodo, int b, int e, int izq, int der){
    int L=2*nodo+1,R=L+1,mid=(b+e)/2;
    if(b>=izq && e<=der){
        return T[nodo];
    }
    if(der<=mid){
        return query(L,b,mid,izq,der);
    }
    if(izq>=mid+1){
        return query(R,mid+1,e,izq,der);
    }
    return max(query(L,b,mid,izq,der),query(R,mid+1,e,izq,der));
}
vi G[tam];
vll C;
int dp[tam][20];
int depth[tam];
ll peso[tam];
void init(int nodo,int p ,int d,int P){
    peso[nodo]=P;
    depth[nodo]=d;
    dp[nodo][0]=p;
    for(int i=0;i<G[nodo].size();i++){
        int it=G[nodo][i];
        if(it==p)continue;
        init(it,nodo,d+1,P+C[it-1]);
    }
}
void initbl(){
    init(0,-1,0,1e9);
    for(int i=1;i<=19;i++){
        for(int l=0;l<tam;l++){
            if(dp[l][i-1]==-1)continue;
            dp[l][i]=dp[dp[l][i-1]][i-1];
        }
    }
}
pair<ll,ll> _find(int nodo, int num){//retorna la suma y el indice
    int nodoin=nodo;
    for(int i=19;i>=0;i--){
        if(nodo==-1)return {0,0};
        if(num&(1<<i)){
            nodo=dp[nodo][i];
        }
    }
    return {peso[nodoin]-peso[nodo]+C[nodo-1],nodo};

}
int main()
{
    ll n,q,d,c;
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>d>>c;
        v.pb(d);C.pb(c);
    }
    v.pb(5000);
    init(0,0,n);
    for(int i=0;i<n;i++){
        int b=i+1,e=n;
        int pos;
        while(b<=e){
            int mid=(b+e)/2;
            ll Q=query(0,0,n,b,mid);
            if(b==e){
                pos=b;
                break;
            }
            if(Q>v[i]){
                pos=mid;
                e=mid;
            }else{
                b=mid+1;
                pos=e;
            }
       }
       if(pos==n){
            G[i+1].pb(0);G[0].pb(i+1);
       }else{
            G[i+1].pb(pos+1);G[pos+1].pb(i+1);
       }
    }
    initbl();
    ll R,V;
    while(q--){
        cin>>R>>V;
        int b=0,e=depth[R];
        int res=0,aux=20;
        while(b<=e && aux--){
            int mid=(b+e)/2;
            pair<ll,ll> Q=_find(R,mid);
            if(Q.F>=V){
                res=Q.S;
                e=mid;
            }else{
                b=mid+1;
            }
        }
        if(res>n)res=0;
        cout<<res<<endl;
    }

    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'void init(int, int, int, int)':
fountain.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0;i<G[nodo].size();i++){
      |                 ~^~~~~~~~~~~~~~~
fountain.cpp: In function 'int main()':
fountain.cpp:101:26: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
  101 |             G[i+1].pb(pos+1);G[pos+1].pb(i+1);
      |                       ~~~^~

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