Submission #157913

#	Time	Username	Problem	Language	Result	Execution time	Memory
157913		HungAnhGoldIBO2020	Cake 3 (JOI19_cake3)	C++14	24 / 100	4062 ms	7116 KiB

cake3

#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("O3")
using namespace std;
const int N=2e5+1;
const int LOG=18;
const long long inf=1e18+2;
long long bit_sum[N],ans[N];
int n,num,bit_cnt[N],nowl=1,nen[N],nowr=0,idx[N];
pair<int,int> lis[N];
queue<pair<pair<int,int>,pair<int,int> > > dac_lis;
void upd(int pos,int val){
	while(pos<=n){
		bit_sum[pos]+=val;
		if(val>=0){
			++bit_cnt[pos];
		}
		else{
			--bit_cnt[pos];
		}
		pos+=(pos&-pos);
	}
}
long long get_sum(int x){			//sum of first x number
	long long sum=0;
	for(int i=0,j=LOG-1;j>=0;--j){
		if(i+(1<<j)<=n&&bit_cnt[i+(1<<j)]<=x){
			x-=bit_cnt[i+(1<<j)];
			sum+=bit_sum[i+(1<<j)];
			i+=(1<<j);
		}
		if(x==0){
			break;
		}
	}
	return sum;
}
void solve(int l,int r,int lef,int rig){
	if(r-lef<num-1){
		for(int i=l;i<=r;++i){
			ans[i]=-inf;
		}
		return;
	}
	int mid=(l+r)>>1,idxmax=0;
	long long max1;
	ans[mid]=-inf;
	if(nowl>rig||nowr<l){
		memset(bit_cnt,0,sizeof(bit_cnt));
		memset(bit_sum,0,sizeof(bit_sum));
		nowl=1;
		nowr=0;
	}
	while(nowr<mid){
		++nowr;
		upd(n-nen[nowr]+1,lis[nowr].first);			//take the max so just reverse them
	}
	while(nowl<=rig&&nowr-nowl+1>=num){
		if(nowl>=lef&&nowl<=rig){
			max1=get_sum(num)-lis[mid].second+lis[nowl].second;
			if(ans[mid]<max1){
				ans[mid]=max1;
				idxmax=nowl;
			}
		}
		if(nowl==rig){
			break;
		}
		upd(n-nen[nowl]+1,-lis[nowl].first);
		++nowl;
	}
	if(l<mid){
		dac_lis.push({{l,mid-1},{lef,idxmax}});
	}
	if(mid<r){
		dac_lis.push({{mid+1,r},{idxmax,rig}});
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int i;
	srand(time(0));
	cin>>n>>num;
	for(i=1;i<=n;++i){
		cin>>lis[i].first>>lis[i].second;
		lis[i].second<<=1;
		idx[i]=i;
	}
	sort(lis+1,lis+1+n,[&](pair<int,int> x,pair<int,int> y){
		return x.second<y.second;
	});
	sort(idx+1,idx+1+n,[&](int x,int y){
		return lis[x].first<lis[y].first;
	});
	for(i=1;i<=n;++i){
		nen[idx[i]]=i;
	}
	dac_lis.push({{1,n},{1,n}});
	while(dac_lis.size()){
		pair<pair<int,int>,pair<int,int> > lis1=dac_lis.front();
		dac_lis.pop();
		solve(lis1.first.first,lis1.first.second,lis1.second.first,lis1.second.second);
	}
	cout<<*max_element(ans+1,ans+1+n);
}

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