Submission #376988

#	Time	Username	Problem	Language	Result	Execution time	Memory
376988		8e7	Cake 3 (JOI19_cake3)	C++14	100 / 100	1558 ms	7528 KiB

cake3

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#define ll long long
#define maxn 200005

#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

const int maxb = 1<<18;

int n, m;
vector<int> v;
inline int id(int x) {
	return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

int bit[maxb + 1];
inline void modify(int ind, int val) {
	for (;ind <= maxb;ind += ind & (-ind)) bit[ind] += val;
}
inline int kthsmall(int k) { //1 indexed
	int ret = 0;
	for (int i = 17;i >= 0;i--) {
		if (bit[ret + (1<<i)] < k) {
			k -= bit[ret + (1<<i)];
			ret += 1<<i;
		}
	}
	return ret + (k ? 1: 0);
}
inline int query(int ind) {
	int ret = 0;
	for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
	return ret;
}
pii a[maxn];
inline bool cmp(pii a, pii b) {
	return a.ss < b.ss;
}


ll sum = 0;
int siz = 0;

inline void add(int ind) {
	//cout << a[ind].ff << endl;
	int p = id(a[ind].ff);
	modify(p, 1);
	int pos = query(p);
	siz++;
	//cout << 1 << "  " << a[ind].ff << endl;
	//cout << sum << endl;
	if (pos > siz - m) {
		sum += a[ind].ff;
		//cout << a[ind].ff << endl;
	}
	if (pos > siz - m && siz > m) {
		int x = kthsmall(siz - m);
		sum -= v[x - 1];
		//cout << -v[x - 1] << endl;
	}
}
inline void rem(int ind) {

	int p = id(a[ind].ff);
	int pos = query(p);
	modify(p, -1);

	//cout << "  " << pos << endl;
	if (pos > siz - m && siz > m) { // removing from big
		siz--;
		sum -= a[ind].ff;
		//cout << -a[ind].ff << endl;
		sum += v[kthsmall(siz - m + 1) - 1];
		//cout << v[kthsmall(siz - m + 1) - 1] << endl;
	} else {
		siz--;
	}
}
int curl = 0, curr = 0;

inline void ins(int l, int r) {
	while (curl > l) curl--, add(curl);
	while (curr < r) add(curr), curr++;
	while (curl < l) rem(curl), curl++;
	while (curr > r) curr--, rem(curr);
	//cout << l << " " << r << " " << sum << " " << siz << endl;
}

ll ans = -(1LL<<60);
void solve(int l, int r, int ql, int qr) {
	if (r <= l || qr <= ql) return;
	if (qr - ql == 1) {
		for (int i = l;i < r;i++) {
			ins(ql, i + 1);
			ans = max(ans, sum - 2 * (a[i].ss - a[ql].ss));
		}
		return;
	}
	int mid = (l + r) / 2;
	ll best = -(1LL<<60), bind = 0;

	for (int i = min(qr - 1, mid - m + 1);i >= ql;i--) {
		ins(i, mid + 1);
		ll val = sum - 2 * (a[mid].ss - a[i].ss);
		if (val > best) {
			best = val;
			bind = i;
		}
	}
	ans = max(ans, best);
	solve(l, mid, ql, bind + 1);
	solve(mid + 1, r, bind, qr);
}
int main() {
	io
	cin >> n >> m;
	for (int i = 0;i < n;i++) {
		cin >> a[i].ff >> a[i].ss;
		v.push_back(a[i].ff);
	}
	sort(a, a + n, cmp);
	sort(v.begin(), v.end());


	for (int i = 0;i < m;i++) {
		add(i);
	}
	curr = m;

	solve(m - 1, n, 0, n);
	cout << ans << "\n";

}
/*
5 3
2 1
4 2
6 4
8 8
10 16

8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879


7 3
3 4
2 5
6 5
4 6
1 7
8 8
5 9

 */

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