제출 #130505

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
130505		Bodo171	Cake 3 (JOI19_cake3)	C++14	100 / 100	939 ms	12024 KiB

cake3

#include <iostream>
#include <fstream>
#include <climits>
#include <algorithm>
#include <cassert>
using namespace std;
const int nmax=200005;
pair<int,int> v[nmax],nrm[nmax];
pair<int,long long> aib[nmax];
long long glob=LLONG_MIN;
int act[nmax];
int n,i,j,k;
inline int lbit(int x)
{
    return (((x^(x-1))&x));
}
void update(int poz,int v1,long long v2)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
        aib[idx].first+=v1,aib[idx].second+=v2;
}
long long best_k(int k)
{
    int ret=0,poz=0;
    long long sum=0;
    for(int p=17;p>=0;p--)
        if(poz+(1<<p)<=n&&ret+aib[poz+(1<<p)].first<=k)
        {
            poz+=(1<<p);
            ret+=aib[poz].first;
            sum+=aib[poz].second;
        }
    return sum;
}
int ap[nmax];
void baga(int poz)
{
    ap[poz]++;
    update(act[poz],1,v[poz].second);
}
void scoate(int poz)
{
    ap[poz]--;
    update(act[poz],-1,-v[poz].second);
}
long long get_cost(int l,int r)
{
    if(r-l+1<k) return LLONG_MIN;
    return -2LL*(v[r].first-v[l].first)+1LL*best_k(k);
}
void divide(int st,int dr,int optst,int optdr)
{
    int m=(st+dr)/2,opt=0;
    long long val,mx=LLONG_MIN;
    if(st>dr) return;
    //ne asiguram ca e bagat tot intervalul [optdr+1,st-1] inainte de asta
    for(int i=max(st,optdr+1);i<=m;i++)
        baga(i);
    for(int i=min(optdr,m);i>=optst;i--)
    {
        baga(i);
        val=get_cost(i,m);
        if(val>mx)
            mx=val,opt=i;
        if(val>glob)
            glob=val;
    }
    if(!opt) opt=optst;
    //acum e bagat tot [optst;m]
    for(int i=optst;i<=min(optdr,m);i++)
       scoate(i);
    //acum e bagat [optdr+1;m]
    divide(m+1,dr,opt,optdr);
    for(int i=opt+1;i<=min(optdr,m);i++)
        baga(i);
    //acum e bagat [opt+1;m]
    for(int i=max(st,opt+1);i<=m;i++)
        scoate(i);
    //acum e bagat[opt+1;st-1]
    divide(st,m-1,optst,opt);
    for(i=opt+1;i<=min(optdr,st-1);i++)
        scoate(i);
    //acum e bagat [optdr+1,st-1] din nou
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>k;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].second>>v[i].first;
    }
    sort(v+1,v+n+1);
    for(i=1;i<=n;i++)
    {
        nrm[i].first=v[i].second;
        nrm[i].second=i;
    }
    sort(nrm+1,nrm+n+1);
    reverse(nrm+1,nrm+n+1);
    for(i=1;i<=n;i++)
        act[nrm[i].second]=i;
    for(i=n-k+2;i<k;i++)
        baga(i);
    divide(k,n,1,n-k+1);
    cout<<glob;
    return 0;
}

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