Submission #331218

#	Time	Username	Problem	Language	Result	Execution time	Memory
331218		EIMONIM	Cake 3 (JOI19_cake3)	C++14	0 / 100	4073 ms	384 KiB

cake3

#include <bits/stdc++.h>
#define int int64_t
#define vi vector<int>
#define ii pair<int,int>
#define vb vector<bool>
#define vvi vector<vi>
#define vvb vector<vb>
#define vii vector<ii>
#define vvii vector<vii>
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
using namespace std;
const int INF = 1e18, MOD = 1e9 + 7;


const int MAXN = 2e5+10;
int n,m;
ii a[MAXN];
struct Data{
    int l=0,r=-1;
    multiset<int> best, reserve;
    int res = 0;
    void add(int v){
        if (best.size()==m){
            auto it = best.begin();
            if (*it < v){
                res += v - *it;
                reserve.insert(*it);
                best.erase(it);
                best.insert(v);
            }
            else reserve.insert(v);
        }
        else best.insert(v), res += v;
    }
    void remove(int v){
        auto it = best.find(v);
        if (it != best.end()){
            res -= *it;
            best.erase(it);
            if (reserve.size()){
                auto rit = --reserve.end();
                res += *rit;
                best.insert(*rit);
                reserve.erase(rit);
            }
        }
        else{
            reserve.erase(reserve.find(v));
        }
    }
    void update(int aa, int bb){
        if (aa > r || bb < l){
            while(l<=r) remove(l++);
            l = aa, r = aa-1;
        }
        while(bb>r) add(a[++r].y);
        while(aa<l) add(a[--l].y);
        while(bb<r) remove(a[r--].y);
        while(aa>l) remove(a[l++].y);
    }
    int get(){
        if (best.size()<m) return -INF;
        return res;
    }
} data;
int ans = -INF;
void solve(int l, int r, int optl, int optr){
    if (r<l) return ;
    int i = (l+r)/2;
    if (i-optl + 1 < m){ // cant do i
        solve(l, i-1, optl, optr);
        return ;
    }
    int opt = optl, bestv = -INF;
    loop(j,optl,optr+1){
        if (i-j+1<m) break;
        data.update(j, i);
        int v = data.get() - (a[i].x - a[j].x);
        if (bestv < v){
            bestv = v;
            opt = j;
        }
    }
    chkmax(ans, bestv);
    solve(l, i-1, optl, opt);
    solve(i+1, r, opt, optr);
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin>>n>>m;
    loop(i,0,n) cin>>a[i].y>>a[i].x, a[i].x*=2;
    sort(a, a+n);
    solve(m-1,n-1,0,n-m);
    cout<<ans<<endl;
    return 0;
}
/*
color a
cls
g++ cake3.cpp -o a & a
5 3
2 1
4 2
6 4
8 8
10 16



*/

Compilation message (stderr)

cake3.cpp: In member function 'void Data::add(int64_t)':
cake3.cpp:30:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   30 |         if (best.size()==m){
      |             ~~~~~~~~~~~^~~
cake3.cpp: In member function 'int64_t Data::get()':
cake3.cpp:69:24: warning: comparison of integer expressions of different signedness: 'std::multiset<long int>::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long int'} [-Wsign-compare]
   69 |         if (best.size()<m) return -INF;
      |             ~~~~~~~~~~~^~

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