Submission #133158

#	Time	Username	Problem	Language	Result	Execution time	Memory
133158		hamzqq9	Cake 3 (JOI19_cake3)	C++14	0 / 100	3 ms	376 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 Maxm;
multiset<int> all,best;
int tut[N];

void del(int val) {

	all.erase(all.find(val));

	auto pos=best.find(val);

	if(pos!=best.end()) {

		Maxm-=tut[val];

		best.erase(pos);

		if(sz(all)!=sz(best)) {

			auto pos2=prev(all.lower_bound(*best.begin()));

			best.insert(*pos2);

			Maxm+=tut[*pos2];

		}

	}

}

void add(int val) {

	all.insert(val);

	best.insert(val);

	Maxm+=tut[val];

	if(sz(best)==m+1) {

		Maxm-=tut[*best.begin()];

		best.erase(best.begin());

	}

}

void shift(int w,int to) {

	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;

	r=min(r,pos);

	make(r,pos);

	ans[pos]=-inf;

	int to=-1;

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

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

		ll cur=Maxm-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;

		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:171: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:175: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: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76