Submission #486195

#	Time	Username	Problem	Language	Result	Execution time	Memory
486195		cheissmart	Cake 3 (JOI19_cake3)	C++14	100 / 100	948 ms	183692 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;

vi compress;

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* lc(node* t) {
	return t ? t -> l : nullptr;
}
node* rc(node* t) {
	return t ? t -> r : nullptr;
}

node* h[N];

node* add(node* t, int pos, int tl = 0, int tr = compress.size()) {
	if(tr - tl == 1) {
		node* tt = new node();
		tt -> sum = sum(t) + compress[pos];
		tt -> cnt = cnt(t) + 1;
		return tt;
	}
	int tm = (tl + tr) / 2;
	if(pos < tm)
		return new node(add(lc(t), pos, tl, tm), rc(t));
	else
		return new node(lc(t), add(rc(t), pos, tm, tr));
}


ll qry(node* t1, node* t2, int m, int tl = 0, int tr = compress.size()) {
	if(cnt(t2) - cnt(t1) == m)
		return sum(t2) - sum(t1);
	if(tr - tl == 1)
		return 1LL * compress[tl] * m;
	int tm = (tl + tr) / 2;
	if(cnt(rc(t2)) - cnt(rc(t1)) >= m)
		return qry(rc(t1), rc(t2), m, tm, tr);
	else {
		int x = cnt(rc(t2)) - cnt(rc(t1));
		return sum(rc(t2)) - sum(rc(t1)) + qry(lc(t1), lc(t2), 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;
		compress.PB(a[i].S);
	}	
	sort(ALL(a));
	
	sort(ALL(compress));
	compress.resize(unique(ALL(compress)) - compress.begin());
	
	h[0] = nullptr;
	for(int i = 1; i <= n; i++) {
		int tt = lower_bound(ALL(compress), a[i - 1].S) - compress.begin();
		h[i] = add(h[i - 1], tt);
//		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: 76 / 76