제출 #918810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
918810		amirhoseinfar1385	Cake 3 (JOI19_cake3)	C++17	100 / 100	3972 ms	26332 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
long long n,k;
vector<pair<long long,long long>>all;
long long res=-1e15,inf=1e15;
bool cmp(pair<long long,long long>a,pair<long long,long long>b){
	return a.second<b.second;
}

struct heyyyyy{
	set<pair<long long,long long>>st;
	long long suma,tof;
	pair<long long,long long>manf;
	heyyyyy(){
		manf=make_pair(-1,-1);
		suma=tof=0;
	}
	vector<pair<pair<long long,long long>,pair<long long,long long>>>allv;
	void ins(long long ww,long long ind){
		tof++;
		auto w=make_pair(ww,ind);
		if(st.count(w)==1){
			allv.push_back(make_pair(manf,manf));
			return ;
		}
		if((long long)st.size()<k){
			st.insert(w);
			suma+=ww;
			allv.push_back(make_pair(w,manf));
			return ;
		}
		if((*st.begin())>=w){
			allv.push_back(make_pair(manf,manf));
			return ;
		}
		allv.push_back(make_pair(w,*st.begin()));
		suma-=(*st.begin()).first;
		st.erase(*st.begin());
		suma+=ww;
		st.insert(w);
	}
	long long getmx(){
		if((long long)st.size()<k){
			return -inf;
		}
		return suma;
	}
	long long size(){
		return (long long)allv.size();
	}
	void back(){
		if(allv.back().first==manf){
			allv.pop_back();
			return ;
		}
		auto x=allv.back();
		allv.pop_back();
		if(x.second==manf){
			suma-=x.first.first;
			st.erase(x.first);
			return ;
		}
		suma-=x.first.first;
		suma+=x.second.first;
		st.erase(x.first);
		st.insert(x.second);
	}
}st;

void solve(long long l,long long r,long long tl,long long tr){
	if(l>r){
		return ;
	}
	if(tl==tr){
		int sz=st.size();
		st.ins(all[tl].first,tl);
		for(long long i=max(l,tl);i<=r;i++){
			st.ins(all[i].first,i);
			if(st.getmx()==-inf||i<tl){
				continue;
			}
			res=max(res,st.getmx()-(all[i].second-all[tl].second)*2);
		}
		while(st.size()>sz){
			st.back();
		}
		return ;
	}
	long long mid=(l+r)>>1;
	long long sz=st.size();
	for(long long i=mid;i>max(l-1,tr);i--){
		st.ins(all[i].first,i);
	}
	long long mx=-inf,opt=tr;
	for(long long i=min(mid,tr);i>=tl;i--){
		st.ins(all[i].first,i);
		if(st.getmx()==-inf){
			continue;
		}
		if(mx<st.getmx()-(all[mid].second-all[i].second)*2){
			mx=st.getmx()-(all[mid].second-all[i].second)*2;
			opt=i;
		}
	}
	res=max(res,mx);
	while(st.size()>sz){
		st.back();
	}
	for(long long i=max(l,tr+1);i<=mid;i++){
		st.ins(all[i].first,i);
	}
	solve(mid+1,r,opt,tr);
	while(st.size()>sz){
		st.back();
	}
	for(long long i=opt+1;i<min(l,tr+1);i++){
		st.ins(all[i].first,i);
	}
	solve(l,mid-1,tl,opt);
	while(st.size()>sz){
		st.back();
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	all.resize(n);
	for(long long i=0;i<n;i++){
		cin>>all[i].first>>all[i].second;
	}
	sort(all.begin(),all.end(),cmp);
	solve(k-1,n-1,0,n-1);
	cout<<res<<'\n';
}

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