Submission #364158

#	Time	Username	Problem	Language	Result	Execution time	Memory
364158		cpp219	Cake 3 (JOI19_cake3)	C++14	24 / 100	4050 ms	12396 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 = 3e5 + 69;
const ll mod = 1e16 + 7;
typedef pair<int,int> LL;

int n,m,id[N],cur = 1,lf,rg;
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;
        if (v > 0) st[id].on++;
        else st[id].on--;
        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 lessf(LL x,LL y){
    return x.sc < y.sc;
}

ll process(int l,int r){
    //cout<<lf<<" "<<rg<<" x "<<l<<" "<<r<<"\n";
    if (rg > r&&rg) upd(1,1,n,id[rg],-a[rg].fs);
    if (lf < l&&lf) upd(1,1,n,id[lf],-a[lf].fs);
    while(rg < r){
        rg++;
        upd(1,1,n,id[rg],a[rg].fs);
    }
    while(rg > r){
        rg--; if (rg == r) break;
        upd(1,1,n,id[rg],-a[rg].fs);
    }
    while(lf > l){
        lf--;
        upd(1,1,n,id[lf],a[lf].fs);
    }
    while(lf < l){
        lf++; if (lf == l) break;
        upd(1,1,n,id[lf],-a[lf].fs);
    }
    return Get(1,1,n,m);
}

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 = now;i <= R;i++){
        ll kq = process(now,i) - 2*(a[i].sc - a[now].sc);
        //cout<<Get(1,1,n,m)<<" "<<now<<" "<<i<<"\n";
        if (i - now + 1 >= m){
            if (kq > cur_ans) cur_ans = kq,pos = i;
        }

    }
    final_ans = max(final_ans,cur_ans);
    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 "tst"
    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,lessf);
    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:95:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   95 |     for (ll i = 1;i <= n;i++) cin>>a[i].fs>>a[i].sc; sort(a + 1,a + n + 1,lessf);
      |     ^~~
cake3.cpp:95:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   95 |     for (ll i = 1;i <= n;i++) cin>>a[i].fs>>a[i].sc; sort(a + 1,a + n + 1,lessf);
      |                                                      ^~~~
cake3.cpp:96:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   96 |     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:96:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   96 |     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:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   91 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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