Submission #572203

#	Time	Username	Problem	Language	Result	Execution time	Memory
572203		Deepesson	Cake 3 (JOI19_cake3)	C++17	5 / 100	4058 ms	1492 KiB

cake3

#include <bits/stdc++.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,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];

typedef std::pair<ll,ll> pll;
///Eu sei como resolver para um M infinito, mas como faco para um M FINITO???
///Ideia do M infinito:
///O custo do absoluto eh basicamente MAX*2 - MIN*2
///O resto N importa muito, eu tenho que pegar a soma dos M-2 maiores elementos entre L e R (alem da soma do A de L e R)
///Relaxacao lagrangiana talvez?

///Dividir para conquistar?

int N,M;
const ll inf = (1LL<<60LL);
std::vector<pll> vec;
long long pode=0;
long long resp=-inf;
long long consulta(int l,int r,int p){///Naive
    {
        std::vector<long long> v;
        for(int i=l;i<=r;++i){
            v.push_back(vec[i].second);
        }
        std::sort(v.begin(),v.end(),std::greater<long long>());
        if(v.size()<p)return -inf;
        long long ans=0;
        for(int j=0;j!=std::min((int)v.size(),p);++j){
            ans+=v[j];
        }
        return ans;
    }
    if(r<l)return -inf;
    if(r-l+1<p)return -inf;
    ans=0;restante=p;
    auto beta = &locais[r],alpha=&memoria[0];

    if(l){
        alpha=&locais[l-1];
    }
    walk(beta,alpha);
    return ans;
}
int count=0;
void dp(int l,int r,int la,int ra){
    if(r<l)return;
    int m = (l+r)/2;
    ll ans = -inf,split=m;
    ++count;
    for(int i=0;i<=std::min(MAX,m-1);++i){
        ll que = consulta(i+1,m-1,M-2);
        ll bonus = que-(2LL*vec[m].first)+vec[m].second+vec[i].second+(2LL*vec[i].first);
        ///std::cout<<bonus<<" "<<que<<" "<<i+1<<" "<<m-1<<"!\n";
        if(bonus>ans){
            ans=bonus;
            split=i;
        };
    }
    resp=std::max(resp,ans);
    dp(l,m-1,la,split);
    dp(m+1,r,split,ra);
}

int main()
{
    std::cin>>N>>M;
    for(int i=0;i!=N;++i){
        ll a,b;
        std::cin>>a>>b;
        vec.push_back({b,a});
    }
    std::sort(vec.begin(),vec.end());

    for(int i=0;i!=N;++i){
       /// std::cout<<vec[i].first<<" "<<vec[i].second<<"\n";
        if(i)locais[i]=locais[i-1];
        ///Comprimir cordenada!!!!!!!! N sei se precisa, provavelmente n, a arvore eh esparsa
        inserir(&locais[i],vec[i].second,vec[i].second);
    }
    dp(0,N-1,0,N-1);
    assert(count==N);
    std::cout<<resp<<"\n";
}

Compilation message (stderr)

cake3.cpp: In function 'void walk(node*, node*, int, int)':
cake3.cpp:63:9: warning: variable 'tem' set but not used [-Wunused-but-set-variable]
   63 |     int tem = 0;
      |         ^~~
cake3.cpp: In function 'long long int consulta(int, int, int)':
cake3.cpp:101:20: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |         if(v.size()<p)return -inf;
      |            ~~~~~~~~^~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76