Submission #364098

#	Time	Username	Problem	Language	Result	Execution time	Memory
364098		cpp219	Cake 3 (JOI19_cake3)	C++14	24 / 100	4082 ms	15896 KiB

cake3

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 5e5 + 69;
const ll mod = 1e16 + 7;
typedef pair<ll,ll> LL;

ll n,m,id[N],cur = 1;
LL a[N],b[N];
struct Node{
    ll val,on;
};
Node st[4*N];

Node operator + (Node a,Node b){
    Node c = {a.val + b.val,a.on + b.on};
    return c;
}

void upd(ll id,ll l,ll r,ll u,ll v){
    if (u < l||r < u) return;
    if (l == r){
        st[id].val = v; st[id].on = 0;
        if (v) st[id].on = 1;
        return;
    }
    ll mid = (l + r)/2;
    upd(id*2,l,mid,u,v); upd(id*2 + 1,mid + 1,r,u,v);
    st[id] = st[id*2] + st[id*2 + 1];
}

ll Get(ll id,ll l,ll r,ll cnt){
    if (st[id].on <= cnt) return st[id].val;
    ll mid = (l + r)/2;
    if (st[id*2].on <= cnt) return  st[id*2].val + Get(id*2 + 1,mid + 1,r,cnt - st[id*2].on);
    return Get(id*2,l,mid,cnt);
}
bool lf(LL x,LL y){
    return x.sc < y.sc;
}

ll final_ans = -mod;

void f(ll L,ll R,ll fday,ll lday){
    ll now = (fday + lday)/2,pos = R,cur_ans = -mod;
    if (fday > lday) return;
    //for (ll i = 1;i < 4*N;i++) st[i].val = st[i].on = 0;
    for (ll i = now;i <= min(R,n);i++){
        upd(1,1,n,id[i],a[i].fs);
        ll kq = Get(1,1,n,m) - 2*(a[i].sc - a[now].sc);
        if (i - now + 1 >= m){
            if (kq > cur_ans) cur_ans = kq,pos = i;
        }
        //if (fday == 1&&lday == 2) cout<<Get(1,1,n,m)<<" "<<a[i].fs<<" "<<id[i]<<"\n";
    }
    //if (fday == 1&&lday == 2) exit(0);
    //if (L == 1&&R == 3) exit(0);
    for (ll i = now;i <= min(R,n);i++) upd(1,1,n,id[i],0);
    final_ans = max(final_ans,cur_ans);
    //cout<<L<<" "<<R<<" x "<<fday<<" "<<lday<<" = "<<cur_ans<<"\n";
    if (fday == lday) return;
    f(L,pos,fday,now - 1); f(pos,R,now + 1,lday);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        freopen(task".OUT","w",stdout);
    }
    cin>>n>>m;
    for (ll i = 1;i <= n;i++) cin>>a[i].fs>>a[i].sc; sort(a + 1,a + n + 1,lf);
    for (ll i = 1;i <= n;i++) b[i].fs = a[i].fs,b[i].sc = i; sort(b + 1,b + n + 1,greater<LL>());
    for (ll i = 1;i <= n;i++) id[b[i].sc] = i;
    f(1,n,1,n);
    cout<<final_ans;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:77:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   77 |     for (ll i = 1;i <= n;i++) cin>>a[i].fs>>a[i].sc; sort(a + 1,a + n + 1,lf);
      |     ^~~
cake3.cpp:77:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |     for (ll i = 1;i <= n;i++) cin>>a[i].fs>>a[i].sc; sort(a + 1,a + n + 1,lf);
      |                                                      ^~~~
cake3.cpp:78:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |     for (ll i = 1;i <= n;i++) b[i].fs = a[i].fs,b[i].sc = i; sort(b + 1,b + n + 1,greater<LL>());
      |     ^~~
cake3.cpp:78:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   78 |     for (ll i = 1;i <= n;i++) b[i].fs = a[i].fs,b[i].sc = i; sort(b + 1,b + n + 1,greater<LL>());
      |                                                              ^~~~
cake3.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   73 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   74 |         freopen(task".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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