Submission #840613

#	Time	Username	Problem	Language	Result	Execution time	Memory
840613		beepbeepsheep	Cake 3 (JOI19_cake3)	C++17	100 / 100	1384 ms	18204 KiB

cake3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef tree<long long, null_type, less_equal<>,
        rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
#define ll long long
#define ii pair<ll,ll>

#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif

const ll inf=1e15;
const ll maxn=2e5+5;
const ll mod=1e9+7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n,k;
ll dp[maxn],cnt[maxn],fen[maxn],arr[maxn];
pair<ii,ll> ord[maxn];
ll inv[maxn];
ll h[maxn];
ll lptr,rptr;
void upd(ll *arr, ll x, ll v){
	while (x<maxn){
		arr[x]+=v;
		x+=(x&-x);
	}
}
ll query(ll *arr, ll x){
	ll ans=0;
	while (x){
		ans+=arr[x];
		x-=(x&-x);
	}
	return ans;
}
ll query(ll *arr, ll x, ll y){
	return query(arr,y)-query(arr,x-1);
}
void add(ll x){
	upd(cnt,inv[x],1);
	upd(fen,inv[x],arr[x]);
}
void sub(ll x){
	upd(cnt,inv[x],-1);
	upd(fen,inv[x],-arr[x]);
}
ll qry(ll l, ll r){
	while (lptr>l) add(--lptr);
	while (lptr<l) sub(lptr++);
	while (rptr>r) sub(rptr--);
	while (rptr<r) add(++rptr);
	ll le=0,ri=n,m;
	while (le!=ri-1){
		m=(le+ri)>>1;
		if (query(cnt,m,n)>k) le=m;
		else ri=m;
	}
	if (query(cnt,ri,n)!=k) return -inf;
	return query(fen,ri,n)-2*(h[r]-h[l]);
	
}
void dnc(ll l, ll r, ll optl, ll optr){
	if (l>r) return;
	ll m=(l+r)>>1,opt=optl,res=-inf;
	for (int i=optl;i<=min(m,optr);i++){
		res=qry(i,m);
		if (res>dp[m]) dp[m]=res,opt=i;
	}
	dnc(l,m-1,optl,opt);
	dnc(m+1,r,opt,optr);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for (int i=1;i<=n;i++){
		dp[i]=-inf;
		cin>>ord[i].first.second>>ord[i].first.first;
	}
	sort(ord+1,ord+1+n);
	for (int i=1;i<=n;i++){
		h[i]=ord[i].first.first;
		arr[i]=ord[i].first.second;
		ord[i].second=i;
		swap(ord[i].first.first,ord[i].first.second);
	}
	sort(ord+1,ord+1+n);
	for (int i=1;i<=n;i++){
		inv[ord[i].second]=i;
	}
	lptr=1,rptr=1;
	add(1);
	dnc(1,n,1,n);
	cout<<*max_element(dp+1,dp+n+1);
	return 0;
}

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