Submission #219588

#	Time	Username	Problem	Language	Result	Execution time	Memory
219588		manh9203	Cake 3 (JOI19_cake3)	C++17	100 / 100	823 ms	141692 KiB

cake3

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
const int N = 2e5 + 5;

int n, m;
ll V[N], C[N];
pair<ll, ll> a[N];
int inDex[N];
int nNode, rootVer[N];
ll ans;

struct node {
	ll val, cnt, lef, rig;
} st[40 * N];

int build(int l, int r) {
	if (l == r) {
		int id = ++nNode;
		st[id] = {0, 0, 0, 0};
		return id; 
	}
	int mid = (l + r) >> 1;
	int id = ++nNode;
	st[id].lef = build(l, mid);
	st[id].rig = build(mid + 1, r);
	st[id].val = st[id].cnt = 0;
	return id;
}

int update(int old, int l, int r, int i, ll x) {
	if (l == r) {
		int id = ++nNode;
		st[id] = {st[old].val + x, st[old].cnt + 1, st[old].lef, st[old].rig};
		return id;
	}
	int mid = (l + r) >> 1;
	int id = ++nNode;
	if (i <= mid) {
		st[id].lef = update(st[old].lef, l, mid, i, x);
		st[id].rig = st[old].rig;
	} else {
		st[id].lef = st[old].lef;
		st[id].rig = update(st[old].rig, mid + 1, r, i, x);
	}
	st[id].val = st[st[id].lef].val + st[st[id].rig].val;
	st[id].cnt = st[st[id].lef].cnt + st[st[id].rig].cnt;
	return id;
}

ll get(int idL, int idR, int l, int r, int x) {
	if (l == r) {
		return st[idR].val - st[idL].val;
	} else {
		int mid = (l + r) >> 1;
		int L = st[idL].lef, R = st[idR].lef;
		if (st[R].cnt - st[L].cnt < x) {
			ll sum = st[R].val - st[L].val;
			ll hav = st[R].cnt - st[L].cnt;
			L = st[idL].rig; 
			R = st[idR].rig;
			return sum + get(L, R, mid + 1, r, x - hav);
		} else {
			return get(L, R, l, mid, x);
		}
	}
}

void solve(int l, int r, int opL, int opR) {
	if (l > r) return;
	int mid = (l + r) >> 1;
	ll res = -1e18, opt = -1;
	for (int i = opL; i <= min(opR, mid - m + 1); i++) {
		ll tmp = V[i] + V[mid] + get(rootVer[i], rootVer[mid - 1], 1, n, m - 2) - 2 * (C[mid] - C[i]);
		if(tmp > res) {
			res = tmp;
			opt = i;
		}
	}
	ans = max(ans, res);
	solve(l, mid - 1, opL, opt);
	solve(mid + 1, r, opt, opR);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].se >> a[i].fi;
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++) {
		V[i] = a[i].se;
		C[i] = a[i].fi;
		a[i] = {V[i], i};
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++) {
		inDex[a[i].se] = n - i + 1;
	}
	
	rootVer[0] = build(1, n);
	for (int i = 1; i <= n; i++) {
		rootVer[i] = update(rootVer[i - 1], 1, n, inDex[i], V[i]);
	}
	
	ans = -1e18;
	solve(m, n, 1, n);
	cout << ans;
}

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