Submission #546627

#	Time	Username	Problem	Language	Result	Execution time	Memory
546627		Lobo	Cake 3 (JOI19_cake3)	C++17	100 / 100	1305 ms	202616 KiB

cake3

#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;
const int mxv = 1e9;

int n, m;
int trq[32*maxn], trs[32*maxn], f1[32*maxn], f2[32*maxn], st[maxn], perq = 0;
vector<pair<int,int>> cake;

int att(int no, int l, int r, int noant, int pos) {
    if(no == 0) no = ++perq;

    if(l == r) {
        trq[no]++;
        trs[no]+= pos;
        trq[no]+= trq[noant];
        trs[no]+= trs[noant];
        return no;
    }
    
    int mid = (l+r)/2;

    if(pos <= mid) {
        f1[no] = att(f1[no],l,mid,f1[noant],pos);
        f2[no] = f2[noant];
    }
    else {
        f2[no] = att(f2[no],mid+1,r,f2[noant],pos);
        f1[no] = f1[noant];
    }

    trq[no]= trq[f1[no]]+trq[f2[no]];
    trs[no]= trs[f1[no]]+trs[f2[no]];
    return no;
}

int find(int nol, int nor, int l, int r, int val) {
    if(l == r) {
        return val*l;
    }
    int mid = (l+r)/2;
    //vai pra direita
    if(val-(trq[f2[nor]]-trq[f2[nol]]) > 0) {
        return find(f1[nol],f1[nor],l,mid,val-(trq[f2[nor]]-trq[f2[nol]]))+trs[f2[nor]]-trs[f2[nol]];
    }
    else {
        return find(f2[nol],f2[nor],mid+1,r,val);
    }
}

int ans = -inf;
void dc(int l, int r, int opl, int opr) {
    if(l > r) return;
    int mx = -inf;
    int opt = -1;
    int mid = (l+r)/2;

    if(opr-mid+1 < m) {
        dc(l,mid-1,opl,opr);
        return;
    }

    for(int i = opl; i <= opr; i++) {
        if(i-mid+1 < m) continue;
        int qrr = find(mid == 0 ? 0 : st[mid-1],st[i],0,mxv,m) - 2*(cake[i].fr-cake[mid].fr);
    
        if(qrr > mx) {
            mx = qrr;
            opt = i;
        }
    }
    ans = max(ans, mx);
    dc(l,mid-1,opl,opt);
    dc(mid+1,r,opt,opr);
    
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        int v,c; cin >> v >> c;
        cake.pb(mp(c,v));
    }
    sort(all(cake));

    for(int i = 0; i < n; i++) {
        st[i] = att(0,0,mxv,i == 0 ? 0 : st[i-1],cake[i].sc);
    }

    dc(0,n-1,0,n-1);

    cout << ans << endl;

}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

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