oj.uz

Submission #396859

# Submission time Handle Problem Language Result Execution time Memory
396859 2021-04-30T20:02:32 Z Pichon5 Fountain (eJOI20_fountain) C++17
100 / 100
 1254 ms 25108 KB 
#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[4*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()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    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;
        while(b<=e){
            int mid=(b+e)/2;
            pair<ll,ll> Q=_find(R,mid);
            if(b==e){
                res=Q.S;
                break;
            }
            if(Q.F>=V){
                res=Q.S;
                e=mid;
            }else{
                b=mid+1;
            }
        }
        if(res>n)res=0;
        cout<<res<<"\n";
    }

    return 0;
}
//freopen("input.2_03","r",stdin);

Compilation message

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:99:11: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |        if(pos==n){
      |           ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10444 KB Output is correct
2 Correct 17 ms 10556 KB Output is correct
3 Correct 17 ms 10576 KB Output is correct
4 Correct 18 ms 10580 KB Output is correct
5 Correct 18 ms 10640 KB Output is correct
6 Correct 18 ms 10600 KB Output is correct
7 Correct 17 ms 10592 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 23716 KB Output is correct
2 Correct 823 ms 22936 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10444 KB Output is correct
2 Correct 17 ms 10556 KB Output is correct
3 Correct 17 ms 10576 KB Output is correct
4 Correct 18 ms 10580 KB Output is correct
5 Correct 18 ms 10640 KB Output is correct
6 Correct 18 ms 10600 KB Output is correct
7 Correct 17 ms 10592 KB Output is correct
8 Correct 861 ms 23716 KB Output is correct
9 Correct 823 ms 22936 KB Output is correct
10 Correct 18 ms 10584 KB Output is correct
11 Correct 334 ms 15460 KB Output is correct
12 Correct 1254 ms 25108 KB Output is correct
13 Correct 753 ms 23412 KB Output is correct
14 Correct 462 ms 21552 KB Output is correct
15 Correct 383 ms 22324 KB Output is correct