#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(!k)return -1;
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<pll> 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)) + 1;
// 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;
}
// cout<<mid<<" "<<res.first<<endl;
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);
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]);
}
solve(1,n-m+1,m,n);
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |