Submission #364133

#	Time	Username	Problem	Language	Result	Execution time	Memory
364133		cpp219	Cake 3 (JOI19_cake3)	C++14	5 / 100	1791 ms	688 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<ll,ll> LL;

ll n,m,id[N],cur = 1,lf = 1,rg = 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 lessf(LL x,LL y){
    return x.sc < y.sc;
}

ll process(ll l,ll r){
    while(rg <= r){
        upd(1,1,n,id[rg],a[rg].fs); rg++;
    }
    while(rg > r){
        upd(1,1,n,id[rg],0); rg--;
    }
    while(lf >= l){
        upd(1,1,n,id[lf],a[lf].fs); lf--;
    }
    while(lf < l){
        upd(1,1,n,id[lf],0); lf++;
    }
    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 <= min(R,n);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;
        }

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

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