Submission #312512

#	Time	Username	Problem	Language	Result	Execution time	Memory
312512		nathanlee726	Cake 3 (JOI19_cake3)	C++14	100 / 100	3696 ms	13052 KiB

cake3

//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
pii a[200010];
int n,m,ans=-1e18;
struct NODE{
	multiset<int> ms1,ms2;
	int l,r,v;
	NODE():l(0),r(-1),v(0){}
	void ins(int x){
		//cout<<"in "<<x<<" "<<sz(ms1)<<endl;
		if(sz(ms1)>=m){
			if(x>*ms1.begin()){
				v+=(x-*ms1.begin());
				ms2.insert(*ms1.begin());
				ms1.erase(ms1.begin());
				ms1.insert(x);
			}
			else ms2.insert(x);
		}
		else ms1.insert(x),v+=x;
	}
	void rem(int x){
		//cout<<"out "<<x<<endl;
		if(ms1.count(x)){
			//cout<<"cc"<<endl;
			ms1.erase(ms1.find(x));
			v-=x;
			if(ms2.begin()!=ms2.end()){
				//cout<<"ch"<<endl;
				//cout<<"a "<<*ms2.rbegin()<<endl; 
				v+=*(ms2.rbegin());
				ms1.insert(*ms2.rbegin());
				ms2.erase(--ms2.end());
			}
		}
		else {ms2.erase(ms2.find(x));}
	}
}ms;
void change(NODE &ms,int l,int r){
	//cout<<ms.l<<" "<<ms.r<<" "<<l<<" "<<r<<endl;
	//cout<<ms.v<<endl;
	while(r>ms.r)ms.ins(a[++ms.r].X);
	while(l<ms.l)ms.ins(a[--ms.l].X);
	while(r<ms.r)ms.rem(a[ms.r--].X);
	//cout<<"a"<<endl;
	while(l>ms.l)ms.rem(a[ms.l++].X);
	//for(auto i:ms.ms1)cout<<i<<" ";
	//cout<<endl;	
	//for(auto i:ms.ms2)cout<<i<<" ";
	//cout<<endl;
}
bool cmp(pii a,pii b){return(a.Y==b.Y?a.X>b.X:a.Y<b.Y);}
void DAC(int l,int r,int dl,int dr){
	if(l>r)return;
	int s=0,mi=(l+r)/2,opt=-1e18,optp;
	if(mi-dl+1<m){
		DAC(l,mi-1,dl,dr);
		return;
	}
	//cout<<l<<" "<<r<<endl;
	for(int i=dl;i<=mi-m+1&&i<=dr;i++){
		change(ms,i,mi);
		//cout<<i<<endl; 
		if(mi-i+1>=m&&ms.v-2*(a[mi].Y-a[i].Y)>opt)opt=ms.v-2*(a[mi].Y-a[i].Y),optp=i;
	}
	ans=max(ans,opt);
	DAC(l,mi-1,dl,optp),DAC(mi+1,r,optp,dr);
	return;
}
signed main(){
	IOS();
	cin>>n>>m;
	F(n)cin>>a[i].X>>a[i].Y;
	sort(a,a+n,cmp);
	DAC(m-1,n-1,0,n-m);
	cout<<ans<<endl;
return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void DAC(long long int, long long int, long long int, long long int)':
cake3.cpp:107:6: warning: unused variable 's' [-Wunused-variable]
  107 |  int s=0,mi=(l+r)/2,opt=-1e18,optp;
      |      ^
cake3.cpp:119:5: warning: 'optp' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |  DAC(l,mi-1,dl,optp),DAC(mi+1,r,optp,dr);
      |  ~~~^~~~~~~~~~~~~~~~

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