Submission #674097

#	Time	Username	Problem	Language	Result	Execution time	Memory
674097		Cookie	Cake 3 (JOI19_cake3)	C++14	100 / 100	524 ms	10772 KiB

cake3

#include<bits/stdc++.h>

#include<fstream>
//#include "factories.h"

using namespace std;
ifstream fin("sus.in");
ofstream fout("sus.out");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
#define int long long
const int mxn = 3e5, mxv = 1e6;
int n, m, l = 0, r = 0;
ll d[mxn + 1];
vt<ll>b;
struct th{
    ll v, c;
    bool operator <(const th &b){
        return(c < b.c);
    }
};
struct BIT{
    ll bit[mxn + 1];
    void upd(int p, ll v){
        p--;
        while(p <= mxn) {
            bit[p] += v; p |= (p + 1);
        }
    }
    ll get(int p){
        ll ans = 0;
        while(p){
            ans += bit[p - 1]; p &= (p - 1);
        }
        return(ans);
    }
    int kth(int x){
        int pos = 0;
        for(int i = (1 << 17); i; i >>= 1){
            if(pos + i <= mxn && bit[pos + i - 1] < x){
                pos += i; x -= bit[pos - 1];
            }
        }
        return(pos);
    }
};
BIT sm, cnt;
th a[mxn + 1];
void add(int x){
    //cout << a[x].v << " ";
    cnt.upd(a[x].v, 1); sm.upd(a[x].v, b[a[x].v - 1]);
}
void rem(int x){
    cnt.upd(a[x].v, -1); sm.upd(a[x].v, -b[a[x].v - 1]);
}
ll get(){
    int p = cnt.kth(m) + 1; assert(p < mxn);
    ll ans = sm.get(p - 1), lft = m - cnt.get(p - 1); 
    ans += b[p - 1] * lft; 
    //cout << ans << " ";
    return(ans);
}
void solve(int le, int ri, int bestl, int bestr){
    
    if(le > ri)return;
    int mid = (le + ri) >> 1;
    
    while(l > mid)add(--l);
    while(l < mid)rem(l++);
    ll pos = bestr, val = -1e18;
    
    for(int i = bestl; i <= bestr; i++){
        if(i - mid + 1 < m)continue;
        while(r < i)add(++r); while(r > i)rem(r--);
        ll cr = get() -2 * (a[i].c - a[mid].c);
        //cout << l << ' ' << r << " " << get() << "\n";
        if(cr > val){
            val = cr; pos = i;
        }
    }
    
    //cout << pos << ' ';
    d[mid] = val;
    solve(le, mid - 1, bestl, pos); 
    solve(mid + 1, ri, pos, bestr);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    forr(i, 0, n){
        cin >> a[i].v >> a[i].c;
        b.pb(a[i].v);
    }
    sort(b.rbegin(), b.rend());
    for(int i = 0; i < n; i++){
        
        int le = 0, ri = b.size() - 1, res;
        while(le <= ri){
            int mid = (le + ri) >> 1;
            if(b[mid] >= a[i].v){
                res = mid; le = mid + 1;
            }else{
                ri = mid - 1;
            }
        }
        a[i].v = res + 1;
        
    }
    
    sort(a, a + n);
    add(0);
    solve(0, n - 1, 0, n - 1);
    ll ans = -1e18;
    for(int i = 0; i + m - 1 < n; i++){
        
        //cout << d[i] << " ";
         ans = max(ans, d[i]);
    }
    cout << ans;
}

Compilation message (stderr)

cake3.cpp: In function 'void solve(long long int, long long int, long long int, long long int)':
cake3.cpp:83:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   83 |         while(r < i)add(++r); while(r > i)rem(r--);
      |         ^~~~~
cake3.cpp:83:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   83 |         while(r < i)add(++r); while(r > i)rem(r--);
      |                               ^~~~~
cake3.cpp: In function 'int main()':
cake3.cpp:115:22: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |         a[i].v = res + 1;
      |                  ~~~~^~~

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