Submission #148072

#	Time	Username	Problem	Language	Result	Execution time	Memory
148072		WhipppedCream	Cake 3 (JOI19_cake3)	C++17	100 / 100	1171 ms	128428 KiB

cake3

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
 
const int maxn = 2e5+5;
 
vector< ii > vec;
 
int n, k;
 
int v[maxn];
int w[maxn];
 
 
struct node
{
	ll sum;
	int left, right;
	node(){}
	node(ll val, int left, int right) : sum(val), left(left), right(right){}
};
 
node cnt[20*maxn], tot[20*maxn];
 
int tungc = 0;
int tungd = 0;
 
int pos[maxn];
 
int rcnt[maxn], rtot[maxn];
 
int update(node *st, int &tung, int x, int dx, int p, int L, int R)
{
	if(L<= x && x<= R)
	{
		if(L == R)
		{
			tung++;
			st[tung] = node(st[p].sum+dx, 0, 0);
			return tung;
		}
		int M = (L+R)/2;
		int a = update(st, tung, x, dx, st[p].left, L, M);
		int b = update(st, tung, x, dx, st[p].right, M+1, R);
		tung++;
		st[tung] = node(st[a].sum+st[b].sum, a, b);
		return tung;
	}
	return p;
}
 
ll gimme(int p1, int p2, int p3, int p4, ll k, int L, int R)
{
	if(L == R)
	{
		// printf("end at %d %lld\n", L, k);
		if(k> 0) return tot[p4].sum-tot[p3].sum;
		return 0;
	}
	int M = (L+R)/2;
	ll here = (cnt[cnt[p2].right].sum)-(cnt[cnt[p1].right].sum);
	// printf("%d %d right = %lld all %lld\n", L, R, here, cnt[p2].sum-cnt[p1].sum);
	// printf("from %lld+%lld\n", cnt[cnt[p2].left].sum-cnt[cnt[p1].left].sum, cnt[cnt[p2].right].sum-cnt[cnt[p1].right].sum);
	if(here>= k)
	{
		return gimme(cnt[p1].right, cnt[p2].right, tot[p3].right, tot[p4].right, k, M+1, R);
	}
	else
	{
		// printf("adding %lld\n", tot[tot[p4].right].sum-tot[tot[p3].right].sum);
		return (tot[tot[p4].right].sum)-(tot[tot[p3].right].sum)+gimme(cnt[p1].left, cnt[p2].left, tot[p3].left, tot[p4].left, k-here, L, M);
	}
}
 
ll cost(int x, int y)
{
	// printf("querying %d %d\n", x, y);
	return gimme(rcnt[x-1], rcnt[y], rtot[x-1], rtot[y], k-2, 1, n);
}
 
ll ret = -1e18;
 
void solve(int L, int R, int i, int j)
{
	if(L> R) return;
	int M = (L+R)/2;
	pair<ll, int> best = {-1e18, i};
	for(int p = i; p<= min(M-k+1, j); p++)
	{
		//[p..M]
		// printf("cost[%d..%d] = %lld\n", p+1, M-1, cost(p+1, M-1));
		best = max(best, {cost(p+1, M-1)+v[M]+v[p]-2LL*(w[M]-w[p]), p});
	}
	ret = max(ret, best.X);
	solve(L, M-1, i, best.Y);
	solve(M+1, R, best.Y, j);
}
 
int main()
{
	scanf("%d %d", &n, &k);
	vec.resize(n);
	for(int i = 0; i< n; i++)
	{
		scanf("%d %d", &vec[i].Y, &vec[i].X);
	}
	sort(vec.begin(), vec.end());
	for(int i = 1; i<= n; i++)
	{
		v[i] = vec[i-1].Y;
		w[i] = vec[i-1].X;
	}
	cnt[0].sum = tot[0].sum = 0;
	cnt[0].left = cnt[0].right = 0;
	tot[0].left = tot[0].right = 0;
	vector< ii > ayh;
	for(int i = 1; i<= n; i++)
	{
		ayh.pb(ii(v[i], i));
	}
	sort(ayh.begin(), ayh.end());
	for(int i = 0; i< n; i++)
	{
		pos[ayh[i].Y] = i+1;
	}
	// for(int i = 1; i<= n; i++) printf("%d %d\n", v[i], w[i]);
	for(int i = 1; i<= n; i++)
	{
		// printf("updating %d\n", pos[i]);
		rcnt[i] = update(cnt, tungc, pos[i], 1, rcnt[i-1], 1, n);
		rtot[i] = update(tot, tungd, pos[i], v[i], rtot[i-1], 1, n);
	}
	// printf("done\n");
	solve(1, n, 1, n);
	// for(int i = 1; i<= n; i++)
	// {
	// 	for(int j = i+k-1; j<= n; j++)
	// 	{
	// 		ret = max(ret, cost(i+1, j-1)+v[i]+v[j]-2LL*(w[j]-w[i]));
	// 	}
	// }
	printf("%lld\n", ret);
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &vec[i].Y, &vec[i].X);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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