Submission #514597

#	Time	Username	Problem	Language	Result	Execution time	Memory
514597		fatemetmhr	Cake 3 (JOI19_cake3)	C++17	100 / 100	3780 ms	17404 KiB

cake3

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

int n, m, curl, curr;
int v[maxn5], c[maxn5];
int per[maxn5], tc[maxn5];
int tv[maxn5];
ll cost = 0, out;
//vector <int> av;

multiset <int> mx, mn;

inline bool cmp(int i, int j){return c[i] < c[j];}

inline void add(int id){
	//cout << "adding " << id << endl;
	//cout << "______________ " << (*mx.begin()) << endl;
	if(mx.size() < m - 2){
		mx.insert(v[id]);
		cost += v[id];
		//cout << "to mx" << endl;
		return;
	}
	if((*mx.begin()) < v[id]){
		mn.insert((*mx.begin()) * -1);
		//cout << "por " << (*mx.begin()) << endl;
		cost -= (*mx.begin());
		mx.erase(mx.begin());
		mx.insert(v[id]);
		cost += v[id];
		//cout << "to mx with erasing!" << endl;
		return;
	}
	mn.insert(-v[id]);
	//cout << "to mn " << id << endl;
	return;
}

inline void remo(int id){
	//cout << "removing " << id << endl;

	if((*mx.begin()) <= v[id]){
		//cout << "form mx << endl" << endl;
			//cout << "noo " << v[id] << ' ' << id << ' ' << curl << ' ' << curr << endl;
		mx.erase(mx.find(v[id]));
		cost -= v[id];
		if(!mn.empty()){
			mx.insert((*mn.begin()) * -1);
			cost -= (*mn.begin());
			//cout << "wow " << (*mn.begin()) << endl;
			mn.erase(mn.begin());
		}
	}
	else{
		//cout << "from mn " << endl;
			//cout << "em no " << ' ' << curl << ' ' << curr << ' ' << id << endl;
		//cout << "so right " << id << endl;
		mn.erase(mn.find(-v[id]));
	}
	return;
}

inline void calc(int l, int r){
	/*
	av.clear();
	for(int i = l; i <= r; i++)
		av.pb(v[i]);
	sort(all(av));
	cost = av.back() + av[av.size() - 2];
	return;
	*/

	while(curr < r){
		curr++;
		add(curr);
	}
	while(curl > l){
		curl--;
		add(curl);
	}
	while(curr > r){
		remo(curr);
		curr--;
	}
	while(curl < l){
		remo(curl);
		curl++;
	}
	return;
}

inline void solve(int l, int r, int opl, int opr){
	if(l >= r)
		return;
	int mid = (l + r) >> 1;
	int opt = -1;
	ll ans = -1 * inf;
	//cout << l << ' ' << r << ' ' << opl << ' ' << opr << endl;
	for(int i = opl; i < min(mid - m + 2, opr); i++){
		calc(i + 1, mid - 1);
		//cout << i << ' ' << mid << ' ' << cost << endl;
		ll val = 2 * c[i] + cost - 2 * c[mid] + v[i] + v[mid];
		if(ans <= val){
			ans = val;
			opt = i;
		}
	}
	out = max(out, ans);
	if(r - l == 1)
		return;
	solve(l, mid, opl, opt + 1);
	solve(mid + 1, r, opt, opr);
	return;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> v[i] >> c[i];
		per[i] = i;
	}
	sort(per, per + n, cmp);
	for(int i = 0; i < n; i++){
		tv[i] = v[per[i]];
		tc[i] = c[per[i]];
	}
	for(int i = 0; i < n;i ++){
		v[i] = tv[i];
		c[i] = tc[i];
	}
	out = -1 * inf;
	curl = m - 1;
	curr = m - 1;
	mx.insert(v[m - 1]);
	cost = v[m - 1];
	solve(m - 1, n, 0, n);
	cout << out << endl;
}

Compilation message (stderr)

cake3.cpp: In function 'void add(int)':
cake3.cpp:38:15: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |  if(mx.size() < m - 2){
      |     ~~~~~~~~~~^~~~~~~

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