Submission #1204193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204193		shjeong	Cake 3 (JOI19_cake3)	C++20	0 / 100	1 ms	324 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<array<ll,3>> 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].r ? tree[tree[cur].r].cnt - (~prv and ~tree[prv].r ? tree[tree[prv].r].cnt : 0) : 0);
        if(k <= x)return query(tree[prv].r,tree[cur].r,mid+1,e,k);
        return query(tree[prv].l,tree[cur].l,s,mid,k-x);
    }
} seg;
ll root[202020];
vector<pll> cp;
ll ans=-Lnf;
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,m-2);
//    cout<<t<<endl;
    ll ret = -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);
    ans=max(ans,ret);
    return ret;
}
ll opt[202020];
void SMAWK(vector<ll> &R, vector<ll> &C){
    ll n = sz(R), m = sz(C);
    if(!n)return;
    vector<ll> st;
    for(auto i : C){
        if(!sz(st))st.push_back(i);
        else{
            while(sz(st)){
                ll p = f(R[sz(st)-1],st.back()), q = f(R[sz(st)-1],i);
                if(p > q)break;
                st.pop_back();
            }
            if(sz(st) < n)st.push_back(i);
        }
    }
    vector<ll> R2;
    for(int i = 1 ; i < n ; i+=2)R2.push_back(R[i]);
    SMAWK(R2,st);
    for(int i = 0, j = 0 ; i < n ; i+=2){
        ll r = (i==n-1 ? st.back() : opt[R[i+1]]);
        while(j < sz(st) and st[j] <= r){
            if(!opt[R[i]] or f(R[i],opt[R[i]]) < f(R[i],st[j]))opt[R[i]] = st[j];
            j++;
        }
        j--;
    }
}
int main(){
    fast;
    cin>>n>>m;
    v.resize(n);
    ll x=0;
    for(auto &[a,b,c] : v)cin>>b>>a, c=++x, cp.push_back({b,c});
    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][1], C[i] = v[i-1][0];
        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),pll(V[i],v[i-1][2]))-cp.begin(),V[i]);
    }
    vector<ll> R, C;
    for(int i = 1 ; i <= n ; i++)R.push_back(i);
    for(int i = 1 ; i <= n ; i++)C.push_back(i);
    SMAWK(R,C);
    cout<<ans;
}

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