Submission #364189

#	Time	Username	Problem	Language	Result	Execution time	Memory
364189		cpp219	Cake 3 (JOI19_cake3)	C++98	100 / 100	2493 ms	12652 KiB

cake3

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e5 + 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; int on;
};
Node st[1300000];

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

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

ll Get(int id,int l,int r,int 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";
    static int curl = 1, curr = 0;
    while(curr < r)
    {
        ++curr; upd(1,1,n,id[curr],a[curr].fs);
    }
    while(curr > r)
    {
        upd(1,1,n,id[curr],-a[curr].fs);
        --curr;
    }
    while(curl > l)
    {
        --curl;
        upd(1,1,n,id[curl],a[curl].fs);
    }
    while(curl < l)
    {
        upd(1,1,n,id[curl],-a[curl].fs);
        ++curl;
    }
    return Get(1,1,n,m);
}

ll final_ans = -mod;

void f(int L,int R,int fday,int lday){
    if (fday > lday) return;
    int now = (fday + lday)/2,pos = R;
    ll cur_ans = -mod;
    for (ll i = max(now, L);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 - m + 1);
    cout<<final_ans;
}

Compilation message (stderr)

cake3.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
cake3.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      | 
cake3.cpp: In function 'int main()':
cake3.cpp:102:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  102 |     for (ll i = 1;i <= n;i++) cin>>a[i].fs>>a[i].sc; sort(a + 1,a + n + 1,lessf);
      |     ^~~
cake3.cpp:102:54: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  102 |     for (ll i = 1;i <= n;i++) cin>>a[i].fs>>a[i].sc; sort(a + 1,a + n + 1,lessf);
      |                                                      ^~~~
cake3.cpp:103:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  103 |     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:103:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  103 |     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:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   98 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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