Submission #388664

#	Time	Username	Problem	Language	Result	Execution time	Memory
388664		kshitij_sodani	Cake 3 (JOI19_cake3)	C++14	100 / 100	2580 ms	205360 KiB

cake3

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo n,m;
llo ll[200000*30];
llo rr[200000*30];
llo tree[200000*30];


llo ll2[200000*30];
llo rr2[200000*30];
llo tree2[200000*30];

llo ind[200001];
vector<llo> rr3;
vector<llo> rr4;
llo co=0;
llo update(llo no,llo l,llo r,llo i){
	llo cur=co;
	co++;
	ll[cur]=ll[no];
	rr[cur]=rr[no];
	tree[cur]=tree[no];
	if(l==r){
		tree[cur]+=1;
		return cur;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			ll[cur]=update(ll[no],l,mid,i);
		}
		else{
			rr[cur]=update(rr[no],mid+1,r,i);
		}
		tree[cur]=tree[ll[cur]]+tree[rr[cur]];
		return cur;
	}
}
llo query(llo no,llo no2,llo l,llo r,llo k){
	if(l==r){
		return l;
	}
	else{
		llo mid=(l+r)/2;
		if(tree[ll[no2]]-tree[ll[no]]>=k){
			return query(ll[no],ll[no2],l,mid,k);
		}
		else{
			return query(rr[no],rr[no2],mid+1,r,k-(tree[ll[no2]]-tree[ll[no]]));
		}
	}
}
llo co2=0;
llo update2(llo no,llo l,llo r,llo i,llo val){
	llo cur=co2;
	co2++;
	ll2[cur]=ll2[no];
	rr2[cur]=rr2[no];
	tree2[cur]=tree2[no];
	if(l==r){
		tree2[cur]+=val;
		return cur;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			ll2[cur]=update2(ll2[no],l,mid,i,val);
		}
		else{
			rr2[cur]=update2(rr2[no],mid+1,r,i,val);
		}
		tree2[cur]=tree2[ll2[cur]]+tree2[rr2[cur]];
		return cur;
	}
}
llo query2(llo no,llo l,llo r,llo aa,llo bb){
	if(r<aa or l>bb){
		return 0;
	}
	if(aa<=l and r<=bb){
		return tree2[no];
	}
	else{
		llo mid=(l+r)/2;
		return query2(ll2[no],l,mid,aa,bb)+query2(rr2[no],mid+1,r,aa,bb);
	}
}
vector<pair<llo,llo>> ss;
vector<pair<llo,llo>> ee;
llo solve(llo l,llo r){
	llo su=ss[l].b+ss[r].b-2*(ss[r].a-ss[l].a);
	l++;
	r--;
	llo kk=query(rr3[l],rr3[r+1],0,n-1,m-2);
	llo cot=query2(rr4[kk+1],0,n-1,l,r);//+su;
	//cout<<l-1<<":"<<r+1<<":"<<cot<<endl;
	//cout<<kk<<",,"<<endl;
	return cot+su; 
}
llo ans=-1e18;

void solve(int l,int r,int aa,int bb){
	int mid=(l+r)/2;
	pair<llo,llo> ma={-1e18,-1};

	for(int i=max(aa,mid);i<=bb;i++){
		if(i-mid+1>=m){
			//cout<<mid<<":"<<i<<endl;
			pair<llo,llo> cur={solve(mid,i),i};
			if(cur.a>ma.a){
				ma=cur;
			}
		}
	}
//	cout<<mid<<":"<<ma.b<<endl;
	ans=max(ans,ma.a);
	if(mid>l){
		solve(l,mid-1,aa,ma.b);
	}
	if(mid<r){
		solve(mid+1,r,ma.b,bb);
	}

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(llo i=0;i<2*n;i++){
		ll[i]=2*i+1;
		rr[i]=2*i+2;
		ll2[i]=2*i+1;
		rr2[i]=2*i+2;
		co=max(co,rr[i]+1);
		co2=max(co2,rr[i]+1);
	}



	
	for(llo i=0;i<n;i++){
		llo aa,bb;
		cin>>aa>>bb;
		ss.pb({bb,aa});
	}
	sort(ss.begin(),ss.end());
	/*for(auto j:ss){
		cout<<j.a<<":"<<j.b<<endl;
	}*/
	for(llo i=0;i<n;i++){
		ee.pb({-ss[i].b,i});
	}
	sort(ee.begin(),ee.end());
	for(llo i=0;i<n;i++){
		ind[ee[i].b]=i;
	}
	rr3.pb(0);
	for(llo i=0;i<n;i++){
		llo x=update(rr3.back(),0,n-1,ind[i]);
		rr3.pb(x);
	}
	rr4.pb(0);
	for(llo i=0;i<n;i++){
		rr4.pb(update2(rr4.back(),0,n-1,ee[i].b,-ee[i].a));
	}

	solve(0,n-m,0,n-1);
	cout<<ans<<endl;
	return 0;
	llo la=-1;
	
/*	for(auto j:ss){
		cout<<j.a<<"."<<j.b<<endl;
	}*/

	for(llo i=0;i<n;i++){
		llo su=ss[i].b+2*ss[i].a;
		priority_queue<llo> tt;
		pair<llo,llo> ma={-1e18,-1};
		for(llo j=i+1;j<n;j++){
			while(tt.size()>m-2){
				su+=tt.top();
				tt.pop();
			}
			if(j>=la){
				if(j-i-1>=m-2){
					pair<llo,llo> cur={solve(i,j),j};
					if(cur.a>ma.a){
						ma=cur;
					}
				}
			}
			su+=ss[j].b;
			tt.push(-ss[j].b);
		}
		ans=max(ans,ma.a);
		la=ma.b;
	}
	cout<<ans<<endl;





 
 
	return 0;
}
 

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:188:19: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'llo' {aka 'long long int'} [-Wsign-compare]
  188 |    while(tt.size()>m-2){
      |          ~~~~~~~~~^~~~

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