Submission #1082801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082801		phong	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	348 KiB

cake3

#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 15, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, m;
pii a[nmax];
ll best[nmax];
multiset<pii> one, two;
struct node{
    int l, r, from, to;
};
vector<node> adj[50];
ll pre[nmax], suf[nmax];

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + 1 + n, [](pii a, pii b){
        return a.se < b.se;
         });
    pre[0] = suf[n + 1] = -oo;
    for(int i = 1; i <= n; ++i){
        pre[i] = max(pre[i - 1], a[i].fi + 2 * a[i].se);
    }
//    cout << pre[1] << ' ';
    for(int i = n; i >= 1; --i){
        suf[i] = max(suf[i + 1], a[i].fi - 2 * a[i].se);
    }
    adj[1].push_back({1, n, 1, n});
    ll ans = -oo;
    for(int e = 1; e <= 20; ++e){
        if(adj[e].empty()) continue;
        int pos = 1;
        ll cur = 0;
//        cout << endl;
        one.clear();two.clear();
        for(auto [l, r, from, to] : adj[e]){
            int mid = r + l >> 1;
            auto &p = best[mid];
            p = from;
            int ma = -oo;
            for(int i = max(mid, from); i <= to; ++i){
                if(i - mid + 1 < m) continue;
                while(pos < i){
                    one.insert({a[pos].fi, pos});
                    two.insert({pos, a[pos].fi});
                    cur += a[pos].fi;
                    ++pos;
                }
                while(two.size()){
                    auto it = two.begin();
                    pii tx = *it;
                    if(tx.fi <= mid){
                        cur -= tx.se;
                        one.erase({tx.se, tx.fi});
                        two.erase(it);
                    }
                    else break;
                }
                while(one.size() > m - 2){
                    auto it = one.begin();
                    pii tx = *it;
                    cur -= tx.fi;
                    two.erase({tx.se, tx.fi});
                    one.erase(it);
                }
//                if(mid == 1 && i == 3)                    cout << mid  << ' ' << pre[mid] << ' ' << suf[i] << endl;

                if(ma < pre[mid] + suf[i] + cur){
                    ma = pre[mid] + suf[i] + cur;
                    p = i;
                    ans = max(ans, ma);
                }
            }
            if(l < mid) adj[e + 1].push_back({l, mid - 1, from, p});
            if(mid < r) adj[e + 1].push_back({mid + 1, r, p, to});
        }
    }
    cout << ans;
}
/*
5 4
1 2
2 3
3 4
3 5
1 2 1 3 4


*/

Compilation message (stderr)

cake3.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:53:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |             int mid = r + l >> 1;
      |                       ~~^~~
cake3.cpp:75:34: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   75 |                 while(one.size() > m - 2){
      |                       ~~~~~~~~~~~^~~~~~~

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