Submission #104896

#	Time	Username	Problem	Language	Result	Execution time	Memory
104896		antimirage	Cake 3 (JOI19_cake3)	C++14	100 / 100	2221 ms	148440 KiB

cake3

#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 2e5 + 5;

int n, m, sz = 1, root[N];

pair <int, int> a[N];

struct tree{
	int l, r, cnt;
	long long sum;
};

tree t[N * 32];

long long ans = -1e18;

void update (int ov, int nv, int pos, int tl = 1, int tr = 1e9){

	if (tl == tr)
		t[nv].cnt = t[ov].cnt + 1,
		t[nv].sum = t[ov].sum + tl;
		
	else{
		int tm = (tl + tr) >> 1;
		
		if (pos <= tm){
			t[nv].l = ++sz;
			t[nv].r = t[ov].r;
			update( t[ov].l, t[nv].l, pos, tl, tm );
		}
		else{
			t[nv].r = ++sz;
			t[nv].l = t[ov].l;
			update( t[ov].r, t[nv].r, pos, tm + 1, tr );
		}
		t[nv].cnt = t[ t[nv].l ].cnt + t[ t[nv].r ].cnt;
		t[nv].sum = t[ t[nv].l ].sum + t[ t[nv].r ].sum;
	}
}
long long get (int ov, int nv, int k = m, int tl = 1, int tr = 1e9)
{
	if (tl == tr)
		return k * 1ll * tl;
	
	int tm = (tl + tr) >> 1;
	
	if (k > t[ t[nv].r ].cnt - t[ t[ov].r ].cnt)
		return get(t[ov].l, t[nv].l, k - (t[ t[nv].r ].cnt - t[ t[ov].r ].cnt), tl, tm) + (t[ t[nv].r ].sum - t[ t[ov].r ].sum);

	return get(t[ov].r, t[nv].r, k, tm + 1, tr);
} 
void calc (int l, int r, int opl, int opr)
{
	if (l > r) return;
	
	int md = (l + r) >> 1;
	
	int opt = opl;
	long long res = -1e18;
	
	for (int i = opl; i <= min(opr, md - m + 1); i++){
		
		long long sup = get(root[i - 1], root[md]);
		if ( sup - (a[md].fr - a[i].fr) * 2 > res){
			res = sup - (a[md].fr - a[i].fr) * 2;
			opt = i;
		}
	}
	ans = max(ans, res);
	
	calc(l, md - 1, opl, opt);
	calc(md + 1, r, opt, opr);
}

main(){
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++){
		scanf("%d%d", &a[i].sc, &a[i].fr);
	}
	sort(a + 1, a + n + 1);
	
	for (int i = 1; i <= n; i++){
		root[i] = ++sz;
		update(root[i - 1], root[i], a[i].sc);
	}	
	calc( 1, n, 1, n );
	
	cout << ans << endl;
}
/**
5 3                 
2 1
4 2
6 4
8 8
10 16
**/

Compilation message (stderr)

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

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