Submission #486192

#	Time	Username	Problem	Language	Result	Execution time	Memory
486192		cheissmart	Cake 3 (JOI19_cake3)	C++14	24 / 100	337 ms	262148 KiB

cake3

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

void DBG() { cerr << "]" << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...); 
}
#define debug(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)

const int INF = 1e9 + 7, N = 2e5 + 7;
const ll oo = 1e18 + 7;

struct node {
	node *l, *r;
	ll sum, cnt;
	node() {
		l = r = nullptr;
		sum = cnt = 0;
	}
	node(node* _l, node* _r) {
		l = _l, r = _r;
		sum = (l ? l -> sum : 0LL) + (r ? r -> sum : 0LL);
		cnt = (l ? l -> cnt : 0LL) + (r ? r -> cnt : 0LL);
	}
};

ll cnt(node* t) {
	return t ? t -> cnt : 0LL;
}

ll sum(node* t) {
	return t ? t -> sum : 0LL;
}

node* h[N];

node* add(node* t, int pos, int tl = 0, int tr = INF) {
	if(!t) t = new node();
	if(tr - tl == 1) {
		node* tt = new node();
		tt -> sum = t -> sum + pos;
		tt -> cnt = t -> cnt + 1;
		return tt;
	}
	int tm = (tl + tr) / 2;
	if(pos < tm)
		return new node(add(t -> l, pos, tl, tm), t -> r);
	else
		return new node(t -> l, add(t -> r, pos, tm, tr));
}

ll qry(node* t1, node* t2, int m, int tl = 0, int tr = INF) {
	if(!t1) t1 = new node();
	if(!t2) t2 = new node();
	assert(t2 -> cnt - t1 -> cnt >= m);
	if(t2 -> cnt - t1 -> cnt == m)
		return t2 -> sum - t1 -> sum;
	if(tr - tl == 1)
		return 1LL * tl * m;
	int tm = (tl + tr) / 2;
	if(cnt(t2 -> r) - cnt(t1 -> r) >= m)
		return qry(t1 -> r, t2 -> r, m, tm, tr);
	else {
		int x = cnt(t2 -> r) - cnt(t1 -> r);
		return sum(t2 -> r) - sum(t1 -> r) + qry(t1 -> l, t2 -> l, m - x, tl, tm);
	}
}

ll qry(int l, int r, int m) {
	assert(r - l >= m);
	return qry(h[l], h[r], m);
}

signed main() {
	IO_OP;
	int n, m;
	cin >> n >> m;
	m -= 2;
	V<pi> a(n); // c, v
	for(int i = 0; i < n; i++) {
		cin >> a[i].S >> a[i].F;
	}	
	sort(ALL(a));
	
	h[0] = nullptr;
	for(int i = 1; i <= n; i++) {
		h[i] = add(h[i - 1], a[i - 1].S);
//		debug(h[i] -> cnt);
	}
	
	auto cost = [&] (int j, int i) {
		if(i - j - 1 < m) return -oo;
		return 0LL + 2 * a[j].F - 2 * a[i].F + a[i].S + a[j].S + qry(j + 1, i, m);
	};
	
	ll ans = -oo;
	
	function<void(int, int, int, int)> solve = [&] (int l, int r, int ql, int qr) {
		if(l > r)
			return;
		if(r == l) {
			for(int i = ql; i <= qr; i++)
				ans = max(ans, cost(i, l));
			return;
		}
		int m = (l + r) / 2;
		ll mx = -oo, qm = -1;
		for(int i = ql; i <= qr; i++) {
			ll tt = cost(i, m);
			if(tt > mx) {
				mx = tt;
				qm = i;
			}
		}
		assert(qm != -1);
		ans = max(ans, mx);
		solve(l, m - 1, ql, qm);
		solve(m + 1, r, qm, qr);
	};
	solve(m + 1, n - 1, 0, n - 1);

	cout << ans << '\n';
	
}

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