Submission #133188

#	Time	Username	Problem	Language	Result	Execution time	Memory
133188		hamzqq9	Cake 3 (JOI19_cake3)	C++14	100 / 100	1038 ms	17460 KiB

cake3

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
//#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 2000000000000000
#define N 300005
#define MOD 998244353
#define KOK 700		
using namespace std;

int n,m;
int p[2]={1,0};
ii a[N];
ll ans[N];
ll all;
int tut[N];
ll sum[N];
int cnt[N];
int top=0;

void up2(int pos,int val) {

	for(int i=pos;i<=n;i+=i&-i) sum[i]+=val;
	

}

void up1(int pos,int val) {

	for(int i=pos;i<=n;i+=i&-i) cnt[i]+=val;

}

ll get() {

	ll res=0;
	int pos=0;
	int want=top-m;

	for(int i=19;i>=0;i--) {

		if(pos+(1<<i)>n) continue;

		if(cnt[pos+(1<<i)]<=want) {

			pos+=(1<<i);
			res+=sum[pos];
			want-=cnt[pos];

		}

	}

	return all-res;

}

void del(int val) {

	all-=tut[val];
	--top;

	up1(val,-1);
	up2(val,-tut[val]);

}

void add(int val) {

	all+=tut[val];
	++top;

	up1(val,1);
	up2(val,tut[val]);

}

void shift(int w,int to) {

	if(to==0 || to==n+1) return ;

	if(w==0) {

		while(p[0]-1>=to) {

			--p[0];

			add(a[p[0]].st);

		}

		while(p[0]<to) {

			del(a[p[0]].st);

			++p[0];

		}

	}
	else {

		while(p[1]+1<=to) {

			++p[1];

			add(a[p[1]].st);

		}

		while(p[1]>to) {

			del(a[p[1]].st);

			--p[1];

		}

	}

}

void make(int lw,int rw) {

	if(lw<=p[0]) shift(0,lw);

	if(rw>=p[1]) shift(1,rw);

	shift(0,lw);
	shift(1,rw);

}

void f(int bas,int son,int l,int r) {

	if(bas>son) return ;

	int pos=orta;

	int curr=min(r,pos);

	make(curr,pos);

	ans[pos]=-inf;

	int to=-1;

	for(int i=curr;i>=l;i--,shift(0,i)) {

		if(pos-i+1<m) continue;

		ll cur=get()-2*(a[pos].nd-a[i].nd);

		if(cur>=ans[pos]) {

			ans[pos]=cur;
			to=i;

		}

	}

	if(to==-1) {

		for(int i=bas;i<=pos;i++) ans[i]=-inf;

		f(pos+1,son,l,r);

		return ;

	}

	f(bas,pos-1,l,to);
	f(pos+1,son,to,r);

}

int main() {

	map<int,int> mp;

	scanf("%d %d",&n,&m);

	for(int i=1;i<=n;i++) {

		scanf("%d %d",&a[i].st,&a[i].nd);

		mp[a[i].st]++;

	}

	int cnt=0;

	for(auto x:mp) {

		for(int i=0;i<x.nd;i++) {

			tut[++cnt]=x.st;

		}

	}

	for(int i=1;i<=cnt;i++) {

		while(i+1<=cnt && tut[i]==tut[i+1]) i++;

		mp[tut[i]]=i;

	}

	for(int i=1;i<=n;i++) {

		a[i].st=mp[a[i].st]--;

	}

	sort(a+1,a+1+n,[](ii a,ii b) {

		if(a.nd<b.nd) return true;
		if(a.nd>b.nd) return false;

		return a.st>b.st;

	});
 
	f(1,n,1,n);

	printf("%lld",*max_element(ans+1,ans+1+n));
 	
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:190:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:194:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].st,&a[i].nd);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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