Submission #1204181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204181		shjeong	Cake 3 (JOI19_cake3)	C++20	0 / 100	0 ms	320 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define COMP(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define MOD2 998244353
#define sz(x) (ll)x.size()
typedef __int128_t lll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ll, pll> PP;
const ll Lnf = 2e18;
const ll inf = 1e9;
ll n, m;
vector<pll> v;
ll V[202020], C[202020];
struct Node{
    ll l, r, cnt, sum;
    Node(): l(-1), r(-1), cnt(0), sum(0){}
    Node(ll l, ll r, ll cnt, ll sum): l(l), r(r), cnt(cnt), sum(sum){}
};
struct PST{
    vector<Node> tree;
    void init(ll node, ll s, ll e){
        if(s==e)return;
        ll mid = s+e>>1;
        tree[node].l = sz(tree); tree.push_back(Node());
        tree[node].r = sz(tree); tree.push_back(Node());
        init(tree[node].l,s,mid);
        init(tree[node].r,mid+1,e);
    }
    void upd(ll prv, ll cur, ll s, ll e, ll i, ll d){
        tree[cur].sum = tree[prv].sum + d, tree[cur].cnt = tree[prv].cnt + 1;
        if(s^e){
            ll mid = s+e>>1;
            if(i<=mid){
                tree[cur].l = sz(tree); tree.push_back(Node());
                tree[cur].r = tree[prv].r;
                upd(tree[prv].l, tree[cur].l,s,mid,i,d);
            }
            else{
                tree[cur].r = sz(tree); tree.push_back(Node());
                tree[cur].l = tree[prv].l;
                upd(tree[prv].r, tree[cur].r,mid+1,e,i,d);
            }
        }
    }
    ll get_sum(ll prv, ll cur, ll s, ll e, ll l, ll r){
        if(e<l or r<s or cur<0)return 0;
        if(l<=s and e<=r)return tree[cur].sum - (~prv ? tree[prv].sum : 0);
        ll mid = s+e>>1;
        return get_sum(tree[prv].l,tree[cur].l,s,mid,l,r) + get_sum(tree[prv].r,tree[cur].r,mid+1,e,l,r);
    }
    ll get_cnt(ll prv, ll cur, ll s, ll e, ll l, ll r){
        if(e<l or r<s or cur<0)return 0;
        if(l<=s and e<=r)return tree[cur].cnt - (~prv ? tree[prv].cnt : 0);
        ll mid = s+e>>1;
        return get_cnt(tree[prv].l,tree[cur].l,s,mid,l,r) + get_cnt(tree[prv].r,tree[cur].r,mid+1,e,l,r);
    }
    ll query(ll prv, ll cur, ll s, ll e, ll k){
        if(s==e)return s;
        ll mid = s+e>>1;
        ll x = (~tree[cur].l ? tree[tree[cur].l].cnt - (~prv and ~tree[prv].l ? tree[tree[prv].l].cnt : 0) : 0);
        if(k <= x)return query(tree[prv].l,tree[cur].l,s,mid,k);
        return query(tree[prv].r,tree[cur].r,mid+1,e,k);
    }
} seg;
ll root[202020];
vector<ll> cp;
ll f(ll l, ll r){
    if(r-l+1 < m)return -Lnf;
//    cout<<l<<" "<<r<<" "<<seg.get_cnt(root[l],root[r-1],0,sz(cp)-1,0,sz(cp)-1) - (m-2)<<" ";
    ll t = seg.query(root[l],root[r-1],0,sz(cp)-1,seg.get_cnt(root[l],root[r-1],0,sz(cp)-1,0,sz(cp)-1) - (m-2));
//    cout<<t<<endl;
    return -2*(C[r]-C[l]) + V[l] + V[r] + seg.get_sum(root[l],root[r-1],0,sz(cp)-1,t,sz(cp)-1);
}
ll ans=-Lnf;
void solve(ll l, ll r, ll optl, ll optr){
    if(l>r)return;
    ll mid = l+r>>1;
    pll res={-Lnf,optl};
    for(ll i = max(mid,optl) ; i <= optr ; i++){
        ll t = f(mid,i);
        if(t > res.first)res.first=t,res.second=i;
    }
    ans=max(ans,res.first);
    solve(l,mid-1,optl,res.second);
    solve(mid+1,r,res.second,optr);
}
int main(){
    fast;
    cin>>n>>m;
    v.resize(n);
    for(auto &[a,b] : v)cin>>b>>a, cp.push_back(b);
    sort(all(v)); sort(all(cp)); COMP(cp);
    seg.tree.push_back(Node());
    seg.init(0,0,sz(cp)-1);
    for(int i = 1 ; i <= n ; i++){
        V[i] = v[i-1].second, C[i] = v[i-1].first;
        root[i] = sz(seg.tree); seg.tree.push_back(Node());
        seg.upd(root[i-1],root[i],0,sz(cp)-1,lower_bound(all(cp),V[i])-cp.begin(),V[i]);
    }
    solve(1,n-m+1,m,n);
    cout<<ans;
}

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