oj.uz

Submission #529907

# Submission time Handle Problem Language Result Execution time Memory
529907 2022-02-24T02:44:39 Z Deepesson Holiday (IOI14_holiday) C++17
100 / 100
 279 ms 62808 KB 
#include <bits/stdc++.h>
///#include"holiday.h"
#define MAXS 3100000
#define MAX 100005
#define SEG3LIM (1000000007)
using ll = long long;
struct  __attribute__((packed)) node {
    int left;
    int right;
    ll sum;
    int total;
};
node memoria[MAXS];
int cur=1;
int alocar(void){
    return cur++;
}
int sz;
node nodes[MAX];
ll vals[MAX];
void inserir(node* x,ll val,int p,int la=0,int ra=SEG3LIM-1){
    if(la==ra){
        assert(p==la);
        x->total++;
        x->sum+=val;
        return;
    }
    int m = (la+ra)/2;
    if(m>=p){
        auto old = x->left;
        x->left=alocar();
        memoria[x->left]=memoria[old];
        inserir(&memoria[x->left],val,p,la,m);
    }else {
        auto old = x->right;
        x->right=alocar();
        memoria[x->right]=memoria[old];
        inserir(&memoria[x->right],val,p,m+1,ra);
    }
    ll tot = 0,ss=0;
    if(x->left)tot+=memoria[x->left].sum;
    if(x->right)tot+=memoria[x->right].sum;
    if(x->left)ss+=memoria[x->left].total;
    if(x->right)ss+=memoria[x->right].total;
   /// std::cout<<"Node "<<tot<<" "<<ss<<"\n";
    x->sum=tot;
    x->total=ss;
}
long long ans=0,limites,restante=0;
void walk(node* k,node* u,int la=0,int ra=SEG3LIM-1){
    if(!restante||!(k->sum))return;
    long long subsum=0,subtotal=0;
    subsum+=u->sum;
    subtotal+=u->total;
    if(k->total-subtotal<=restante){
        ans+=k->sum-subsum;
        restante-=k->total-subtotal;
       /// std::cout<<"Add "<<k->sum-subsum<<" "<<la<<" "<<ra<<" "<<restante<<"\n";
        return;
    }

    int m=(la+ra)/2;
    int tem = 0;
    if(k->right){
        tem=memoria[k->right].total-memoria[u->right].total;
    }
    if(la==ra){
        ll pega = std::min(restante,k->total-subtotal);
        restante-=pega;
        ans+=((long long)la)*pega;
       /// std::cout<<"Especial "<<pega<<"\n";
        return;
    }
    if(la==ra)return;
    walk(&memoria[k->right],&memoria[u->right],m+1,ra);
    walk(&memoria[k->left],&memoria[u->left],la,m);
}
node locais[MAX];
void prepara(void){
    for(int i=0;i!=sz;++i){
        if(i)locais[i]=locais[i-1];
        ///Comprimir cordenada!!!!!!!! N sei se precisa, provavelmente n, a arvore eh esparsa
        inserir(&locais[i],vals[i],vals[i]);
    }
}
///Se passar consulta para O(log N) eh AC
long long smconsulta(int l,int r,int p){///Naive
    std::priority_queue<int> queue;
    for(int i=l;i!=r+1;++i){
        queue.push(vals[i]);
    }
    ll ans=0;
    while(queue.size()&&p){
        --p;
        ans+=queue.top();
        queue.pop();
    }
    return ans;
}

long long consulta(int l,int r,int p){///Naive
    ans=0;limites=1e7;restante=p;
    auto beta = &locais[r],alpha=&memoria[0];

    if(l){
        alpha=&locais[l-1];
    }
    walk(beta,alpha);
   /// std::cout<<ans<<" "<<l<<" "<<r<<" "<<p<<" "<<beta->sum<<"<-\n";
   /// std::cout<<"Esperado: "<<smconsulta(l,r,p)<<"\n";
    return ans;
}
long long pode=0;
long long resp=0;
long long inicio=0;
void dp(int l,int r,int la,int ra){
    if(r<l)return;
    int m = (l+r)/2;
    ll ans = 0,split=inicio;
    for(int i=la;i<=ra;++i){
        ll dist1=(inicio-i),dist2=(m-inicio);
        ll custo = (std::min(dist1,dist2)*2)+std::max(dist1,dist2);
        ll tem = pode-custo;
        if(tem<=0)continue;
        ll bonus = consulta(i,m,tem);
        if(bonus>ans){
            ans=bonus;
            split=i;
        }
    }
    resp=std::max(resp,ans);
    dp(l,m-1,la,split);
    dp(m+1,r,split,ra);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    sz=n;
    for(int i=0;i!=n;++i){
        vals[i]=attraction[i];
    }
    inicio=start;
    pode=d;
    prepara();
    dp(inicio,n-1,0,inicio);
    return resp;
}

Compilation message

holiday.cpp: In function 'void walk(node*, node*, int, int)':
holiday.cpp:63:9: warning: variable 'tem' set but not used [-Wunused-but-set-variable]
   63 |     int tem = 0;
      |         ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 0 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 0 ms 716 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62020 KB Output is correct
2 Correct 68 ms 62304 KB Output is correct
3 Correct 58 ms 62284 KB Output is correct
4 Correct 57 ms 62212 KB Output is correct
5 Correct 63 ms 57148 KB Output is correct
6 Correct 17 ms 17976 KB Output is correct
7 Correct 31 ms 32128 KB Output is correct
8 Correct 43 ms 38676 KB Output is correct
9 Correct 12 ms 12988 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2508 KB Output is correct
2 Correct 3 ms 2508 KB Output is correct
3 Correct 2 ms 2508 KB Output is correct
4 Correct 6 ms 2380 KB Output is correct
5 Correct 4 ms 2252 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 2 ms 1228 KB Output is correct
8 Correct 2 ms 1228 KB Output is correct
9 Correct 2 ms 1228 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 62096 KB Output is correct
2 Correct 63 ms 62768 KB Output is correct
3 Correct 66 ms 28560 KB Output is correct
4 Correct 5 ms 2380 KB Output is correct
5 Correct 2 ms 1228 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 2 ms 1228 KB Output is correct
8 Correct 279 ms 62808 KB Output is correct
9 Correct 276 ms 62800 KB Output is correct