Submission #243836

#	Time	Username	Problem	Language	Result	Execution time	Memory
243836		mhy908	Cake 3 (JOI19_cake3)	C++14	100 / 100	1098 ms	205672 KiB

cake3

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
#define lb(x, v) lower_bound(x.begin(), x.end(), v)
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<LL, int> pli;
const LL llinf=4e18;

int n, m;
pll arr[200010];
vector<int> id;
LL ans=-llinf;

struct PST{
    struct NODE{
        LL qu; int qu2;
        NODE *l, *r;
        NODE(){qu=0, qu2=0, l=r=nullptr;}
    };
    NODE* root[200010];
    void init(NODE* here, int s, int e){
        if(s==e)return;
        here->l=new NODE;
        here->r=new NODE;
        init(here->l, s, (s+e)/2);
        init(here->r, (s+e)/2+1, e);
    }
    PST(){
        root[0]=new NODE;
        init(root[0], 1, 200000);
    }
    void in(NODE* lv, NODE* lvpr, int s, int e, int num){
        lv->qu=lvpr->qu;
        lv->qu2=lvpr->qu2;
        if(s==e){
            lv->qu+=(LL)id[s-1];
            lv->qu2++;
            return;
        }
        if(num<=(s+e)/2){
            lv->l=new NODE;
            lv->r=lvpr->r;
            in(lv->l, lvpr->l, s, (s+e)/2, num);
        }
        else{
            lv->r=new NODE;
            lv->l=lvpr->l;
            in(lv->r, lvpr->r, (s+e)/2+1, e, num);
        }
        lv->qu=lv->l->qu+lv->r->qu;
        lv->qu2=lv->l->qu2+lv->r->qu2;
    }
    void in(int lv, int num){
        root[lv]=new NODE;
        num=lb(id, num)-id.begin()+1;
        in(root[lv], root[lv-1], 1, 200000, num);
    }
    pli query(NODE* fr, NODE* re, int s, int e, int k){
        if(re->qu2-fr->qu2<=k)return mp(re->qu-fr->qu, re->qu2-fr->qu2);
        if(s==e&&re->qu2-fr->qu2>k)return mp((LL)id[s-1]*k, k);
        pli tmp=query(fr->r, re->r, (s+e)/2+1, e, k);
        if(tmp.S==k)return tmp;
        pli tmp2=query(fr->l, re->l, s, (s+e)/2, k-tmp.S);
        return mp(tmp.F+tmp2.F, tmp.S+tmp2.S);
    }
    LL query(int lv1, int lv2, int k){
        pli tmp=query(root[lv1-1], root[lv2], 1, 200000, k);
        if(tmp.S<k)return -llinf;
        return tmp.F;
    }
}pst;

void DNC(int s, int e, int a, int b){
    if(s>e)return;
    int mid=(s+e)/2, maxnum;
    LL maxx=-llinf;
    for(int i=max(mid, a); i<=b; i++){
        LL tmp=pst.query(mid, i, m);
        if(tmp==-llinf)continue;
        tmp-=2ll*(arr[i].F-arr[mid].F);
        if(maxx<tmp){
            maxx=tmp;
            maxnum=i;
        }
    }
    ans=max(ans, maxx);
    DNC(s, mid-1, a, maxnum);
    DNC(mid+1, e, maxnum, b);
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld", &arr[i].S, &arr[i].F);
        id.eb((int)arr[i].S);
    }
    svec(id); press(id);
    sort(arr+1, arr+n+1);
    for(int i=1; i<=n; i++)pst.in(i, (int)arr[i].S);
    DNC(1, n-m+1, m, n);
    printf("%lld", ans);
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &arr[i].S, &arr[i].F);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp: In function 'void DNC(int, int, int, int)':
cake3.cpp:93:8: warning: 'maxnum' may be used uninitialized in this function [-Wmaybe-uninitialized]
     DNC(s, mid-1, a, maxnum);
     ~~~^~~~~~~~~~~~~~~~~~~~~

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