Submission #139290

#	Time	Username	Problem	Language	Result	Execution time	Memory
139290		Mahmoud_Adel	Cake 3 (JOI19_cake3)	C++14	100 / 100	1206 ms	140380 KiB

cake3

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
const int N = 2e5+5;
ll n, k, cn, ans = -1e18;
ll root[N], lc[N*40], b[N], rc[N*40];
pair<ll, ll> tree[N*40];
vector<pair<ll, ll>> comp;
pair<ll, ll> p[N];
void merge(int node)
{
	tree[node].f = tree[lc[node]].f+tree[rc[node]].f;
	tree[node].s = tree[lc[node]].s+tree[rc[node]].s;
}
void build(int node = 0, int l=0, int r=n-1)
{
	if(l == r)
	{
		tree[node] = {1, comp[l].f};
		//cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl;
		return ;
	}
	int mid = (l+r)>>1;
	lc[node] = ++cn, rc[node] = ++cn;
	build(lc[node], l, mid);
	build(rc[node], mid+1, r);
	merge(node);
	//cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl;
}
void upd(int i, int node, int node2, int l=0, int r=n-1)
{
	tree[node] = tree[node2];
	if(l == r)
	{
		tree[node] = {0, 0};
		//cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl;
		return ;
	}
	int mid = (l+r)>>1;
	if(i > mid)
	{
		rc[node] = ++cn;
		lc[node] = lc[node2];
		upd(i, rc[node], rc[node2], mid+1, r);
	}
	else
	{
		rc[node] = rc[node2];
		lc[node] = ++cn;
		upd(i, lc[node], lc[node2], l, mid);
	}
	merge(node);
	//cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl;
}
bool cmp(pair<ll, ll> a, pair<ll, ll> b)
{
	return a.s < b.s;
}
ll sum2(ll l, ll r)
{
	vector<ll> vec;
	ll ret = 0;
	for(ll i=l; i<=r; i++)
	{
		vec.push_back(p[i].f);
	}
	sort(vec.rbegin(), vec.rend());
	for(ll i=0; i<k; i++) ret += vec[i];
	return ret;
}
ll sum(int node1, int node2, ll cnt)
{
	ll cmt = tree[rc[node2]].f-tree[rc[node1]].f;
//	cout << node1 << " " << node2 << " | " << rc[node1] << " " << lc[node1]
//	 << " | " << cmt << " " << cnt << " " << tree[node2].f-tree[node1].f << endl;
	assert(tree[node2].f-tree[node1].f >= cnt);
	if(tree[node2].f-tree[node1].f == cnt) return tree[node2].s-tree[node1].s;
	if(!cnt) return 0;
	else if(cmt >= cnt) return sum(rc[node1], rc[node2], cnt);
	else return sum(rc[node1], rc[node2], cmt) + sum(lc[node1], lc[node2], cnt-cmt); 
}
void solve(ll l, ll r, ll s, ll e)
{
	if(l > r) return ;
	ll id = -1, m = -1e18;
	ll mid = (l+r)>>1;
	for(ll i=max(mid+k-1, (ll)s); i<=e; i++)
	{
		ll tmp;
		if(tree[root[mid]].f-tree[root[i+1]].f >= k) tmp = sum(root[i+1], root[mid], k);
		else tmp = sum2(mid, i);
		tmp -= (p[i].s-p[mid].s)*2LL;
		if(tmp > m)  m = tmp, id = i;
	}
	solve(l, mid-1, s, id);
	solve(mid+1, r, id, e);
	ans = max(ans, m);
}
	
int main()
{
	cin >> n >> k;
	for(int i=0; i<n; i++) scanf("%lld %lld", &p[i].f, &p[i].s);
	sort(p, p+n, cmp);
	for(int i=0; i<n; i++) comp.push_back({p[i].f, i});
	sort(comp.begin(), comp.end());
	for(int i=0; i<n; i++) b[comp[i].s] = i;
	build();
	for(int i=1; i<=n; i++)
	{
		int id = b[i-1];
		root[i] = ++cn;
		upd(id, root[i], root[i-1]);
	}
	//cout << sum(root[6+1], root[1], k) << " " << sum2(1, 6) << endl;
	solve(0, n-k, 0, n-1);
	cout << ans << endl;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:105:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; i++) scanf("%lld %lld", &p[i].f, &p[i].s);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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