Submission #1298254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298254		lmaobruh	Cake 3 (JOI19_cake3)	C++20	0 / 100	1 ms	576 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define pb push_back
#define fi first
#define se second
#define ii pair<int,int>
#define ve vector
#define all(x) x.begin(), x.end()
#define fo(i,a,b) for (int i=(a); i<=(b); ++i)
#define fd(i,a,b) for (int i=(a); i>=(b); --i)
#define maxi(a, b) a = max(a, b)
#define mini(a, b) a = min(a, b)
#define siz(x) ((int)(x).size())
#define vi ve<int>
#define _ << ' ' <<

const int N = 5e5+5, inf = 1e9+10, mod = 1e9+7;

bool MBE;

/**

**/

struct BIT {
    ll f[N];
    void upd(int x, ll v) {
        for (; x; x-=x&-x) {
            f[x] += v;
        }
    }
    ll get(int x) {
        ll res = 0;
        for (; x<N; x+=x&-x) {
            res += f[x];
        }
        return res;
    }
    int topk(int k) {
        int l=1, r=2e5, mid, res=-1;
        while (l <= r) {
            mid=(l+r)/2;
            if (get(mid)>=k) res=mid, l=mid+1;
            else r=mid-1;
        }
        return res;
    }
} cnt, sum;

int n, m, cl=1, cr=0;
ii a[N];
vi z;
ll ans=0;

void upd(int p, int v) {
    cnt.upd(a[p].fi,v);
    sum.upd(a[p].fi,v*z[a[p].fi-1]);
}

ll cost(int l, int r) {
    int nx=min(r-l+1,m);
    while (cl<l) upd(cl++,-1);
    while (cr>r) upd(cr--,-1);
    while (cl>l) upd(--cl,1);
    while (cr<r) upd(++cr,1);
    int pos=cnt.topk(nx), tim=nx-cnt.get(pos+1);
    return sum.get(pos+1)+1LL*tim*z[pos-1]-2LL*(a[r].se-a[l].se);
}

void dnc(int l, int r, int optl, int optr) {
    if (l>r) return;
    int mid=(l+r)/2;
    pair<ll,int> best={-1e18,-1};
    fo(i,optl,min(mid-m+1,optr)) {
        best=max(best,pair<ll,int>{cost(i,mid),i});
    }
    maxi(ans,best.fi);
    if (best.se==-1) best.se=optl;
    dnc(l,mid-1,optl,best.se);
    dnc(mid+1,r,best.se,optr);
}

void sol() {
    cin >> n >> m;
    fo(i,1,n) {
        cin >> a[i].fi >> a[i].se;
        z.pb(a[i].fi);
    }
    sort(all(z)); z.resize(unique(all(z))-z.begin());
    sort(a+1, a+n+1, [&](ii x, ii y)->bool{
        if (x.se==y.se) return 0;
        return x.se<y.se;
    });
    fo(i,1,n) {
        a[i].fi=lower_bound(all(z),a[i].fi)-z.begin()+1;
    }
    dnc(1,n,1,n);
    cout << ans;
}

bool MED;

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    if(fopen("A.inp","r")) {
        freopen("A.inp","r",stdin);
        freopen("A.out","w",stdout);
    }
    int tc = 1; // cin >> tc;
    fo(i,1,tc) sol();
//    cerr << "Memory = " << abs(&MED - &MBE)/1024.0/1024.0 << " MB";
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen("A.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
cake3.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen("A.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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