Submission #104829

#	Time	Username	Problem	Language	Result	Execution time	Memory
104829		Just_Solve_The_Problem	Cake 3 (JOI19_cake3)	C++11	100 / 100	1382 ms	248732 KiB

cake3

#include <bits/stdc++.h>

#define fr first
#define sc second
#define ll long long
#define ok puts("ok");

using namespace std;

const int N = (int)2e5 + 7;

pair < ll, ll > ar[N];
int n, m;
ll pref[N], suf[N];
ll ans;
int siz = 1;
int root[N];

struct node {
	int l, r;
	ll sum;
	int cnt;
	node() {
		l = r = 0;
		sum = 0;
		cnt = 0;
	}
};
node tree[N * 50];

void build(int v = 1, int l = 1, int r = n) {
	if (l == r) {
		return ;
	}
	int mid = (l + r) >> 1;
	tree[v].l = ++siz;
	tree[v].r = ++siz;
	build(tree[v].l, l, mid);
	build(tree[v].r, mid + 1, r);
}

void upd(int ov, int nv, int pos, int val, int l = 1, int r = n) {
	if (l == r) {
		tree[nv].sum += val;
		tree[nv].cnt++;
		return ;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) {
		tree[nv].l = ++siz;
		tree[nv].r = tree[ov].r;
		upd(tree[ov].l, tree[nv].l, pos, val, l, mid);
	} else {
		tree[nv].l = tree[ov].l;
		tree[nv].r = ++siz;
		upd(tree[ov].r, tree[nv].r, pos, val, mid + 1, r);
	}
	tree[nv].sum = tree[tree[nv].l].sum + tree[tree[nv].r].sum;
	tree[nv].cnt = tree[tree[nv].l].cnt + tree[tree[nv].r].cnt;
}

ll getsum(int lv, int rv, int l = 1, int r = n, int keep = m - 2) {
	if (keep == 0) return 0;
	if (keep >= tree[rv].cnt - tree[lv].cnt) {
		return tree[rv].sum - tree[lv].sum;
	} 
	int mid = (l + r) >> 1;
	return getsum(tree[lv].l, tree[rv].l, l, mid, max(keep - (tree[tree[rv].r].cnt - tree[tree[lv].r].cnt), 0)) + getsum(tree[lv].r, tree[rv].r, mid + 1, r, keep);
}

ll get(ll l, ll r) {
	return getsum(root[l - 1], root[r]);
}

void make(int l, int r, int optl, int optr) {
	if (l > r) return ;
	int mid = (l + r) >> 1;
	int opt = min(max(mid + m - 1, optl), optr);
	ll res = -1e18;
	for (int i = max(mid + m - 1, optl); i <= optr; i++) {
		ll cost = get(mid + 1, i - 1) + ar[mid].fr + ar[i].fr - 2 * (ar[i].sc - ar[mid].sc);
		// cout << mid << ' ' << i << ' ' << cost << endl;
		if (cost > res) {
			res = cost;
			opt = i;
		}
	}
	// cout << "### " << mid << ' ' << res << ' ' << opt << endl;
	if (res > ans) {
		ans = res;
	}
	make(l, mid - 1, optl, opt);
	make(mid + 1, r, opt, optr);
}

void solve() {
	build();
	root[0] = 1;
	vector < pair < int, int > > vx;
	int asd[N];
	for (int i = 1; i <= n; i++) {
		vx.push_back({ar[i].fr, i});
	}
	sort(vx.begin(), vx.end());
	for (int i = 1; i <= n; i++) {
		asd[vx[i - 1].sc] = i; 
	}
	for (int i = 1; i <= n; i++) {
		root[i] = ++siz;
		upd(root[i - 1], root[i], asd[i], ar[i].fr);
	}
	make(1, n, 1, n);
}

main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld", &ar[i].sc, &ar[i].fr);
	}
	sort(ar + 1, ar + n + 1);
	pref[0] = -1e18;
	for (int i = 1; i <= n; i++) {
		swap(ar[i].fr, ar[i].sc);
		pref[i] = max(pref[i - 1], ar[i].fr + 2 * ar[i].sc);
	}
	suf[n + 1] = -1e18;
	for (int i = n; i >= 1; i--) {
		suf[i] = max(suf[i + 1], ar[i].fr - 2 * ar[i].sc);
	}
	ans = -1e18;
	solve();
	cout << ans;
}

Compilation message (stderr)

cake3.cpp:115:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
cake3.cpp: In function 'int main()':
cake3.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &ar[i].sc, &ar[i].fr);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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