Submission #838756

#	Time	Username	Problem	Language	Result	Execution time	Memory
838756		beaboss	Cake 3 (JOI19_cake3)	C++14	5 / 100	4034 ms	25876 KiB

cake3

// Source: https://oj.uz/problem/view/JOI19_cake3
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)

const ll N = 2e5 + 10;

// const ll N = 1e5;

#define lc i << 1
#define rc (i << 1) + 1


pair<ll, vi> st[4 * N];

ll n, m;
pii inp[N];

pair<ll, vi> comb(pair<ll, vi> a1, pair<ll, vi> b1) { // MODIFY COMBINER FUNCTION
	// combine two sorted vectors
	ll i = 0;
	ll j = 0;
	vi a = a1.s;
	vi b = b1.s;
	ll sum = 0;
	vi vals;

	FOR(_, 0, m) {

		if (i == a.size() && j == b.size()) break;
		if (i == a.size()) {
			vals.pb(b[j]);
			sum+= b[j];
			j++;
		} else if (j == b.size()) {
			vals.pb(a[i]);
			sum+= a[i];
			i++;
		} else if (a[i] > b[j]) {
			vals.pb(a[i]);
			sum+= a[i];
			i++;
		} else {
			vals.pb(b[j]);
			sum+= b[j];
			j++;
		}

	}
	return {sum, vals};
}

void up(ll i) {
	st[i] = comb(st[lc], st[rc]);
}

void update(ll ind, ll val, ll i = 1, ll l = 0, ll r = n) { // update pos ind with value val
	if (l >= r) return;
	if (r - l == 1) {
		st[i] = {val, {val}};
		return;
	}


	ll m = (l + r)/2;

	if (m > ind) update(ind, val, lc, l, m); // contained in left child
	else update(ind, val, rc, m, r); // contained in right child

	up(i); // update current index
}

pair<ll, vi> query(ll ql, ll qr, ll i = 1, ll l = 0, ll r = n) { // query from [ql, qr)
	
	if (l >= r) return {0, {}}; // identity
	if (ql <= l && qr >= r) { // fully contained
		return st[i];
	}

	if (r - l == 1) return {0, {}}; // leaf node

	ll m = (l + r)/2;

	pair<ll, vi> acc = {0, {}}; // SET DEFAULT VALUE

	if (m >= ql) acc = comb(query(ql, qr, lc, l, m), acc);
	if (m <= qr) acc = comb(acc, query(ql, qr, rc, m, r));

	return acc;
}





ll ans = -1e18;

void solve(ll ia, ll ib, ll ja, ll jb) { // solves range [ia, ib) assuming the previous DP can be from [ja, jb]
	if (ia >= ib) return;
	

	ll i = (ia + ib) / 2;
	// if (i-m+1 < ja) {
	// 	solve(i + 1, ib, ja, jb);
	// 	return; // to few numbers
	// }
	assert(i - m + 1 >= ja);

	ll arg_j = 0;

	ll opt = -1e18;

	for (ll j = ja; j <= i-m+1; j++) {
		ll v = query(j, i+1).f - 2 * (inp[i].f - inp[j].f);
		// cout << i << j << v << endl;
		if (v > opt) {
			arg_j = j;
			opt = v;
		}
	}

	ans = max(ans, opt);

	// solve(ia, i, 0, n);
	// solve(i + 1, ib, 0, n);
	solve(ia, i, ja, arg_j);
	solve(max(arg_j + m - 1, i+1), ib, arg_j, jb);

	// ll sum = 0;
	// ll opt = 0;

	// multiset<ll> vals;

	// for (ll j = i; j > i-m; j--) {
	// 	vals.insert(inp[j].s);
	// 	sum+=inp[j].s;
	// }

	// opt = sum - 2ll * (inp[i].f - inp[i-m+1].f);

	// for (ll j = i-m; j >= ja; j--) {
		
	// 	sum += inp[j].s;
	// 	vals.insert(inp[j].s);
	// 	sum -= *vals.begin();
	// 	vals.erase(vals.begin());

	// 	ll v = sum - 2ll * (inp[i].f - inp[j].f);

	// 	if (v > opt) {
	// 		arg_j = j;
	// 		opt=v;
	// 	}
	// }


	

}



int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;

	FOR(i, 0, n) cin >> inp[i].s >> inp[i].f;

	sort(inp, inp + n);

	FOR(i, 0, n) update(i, inp[i].s);
	// cout << query(0, 3).f << endl;
	solve(m-1, n, 0, n);
	cout << ans << endl;

}

Compilation message (stderr)

cake3.cpp: In function 'std::pair<long long int, std::vector<long long int> > comb(std::pair<long long int, std::vector<long long int> >, std::pair<long long int, std::vector<long long int> >)':
cake3.cpp:45:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   if (i == a.size() && j == b.size()) break;
      |       ~~^~~~~~~~~~~
cake3.cpp:45:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   if (i == a.size() && j == b.size()) break;
      |                        ~~^~~~~~~~~~~
cake3.cpp:46:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   if (i == a.size()) {
      |       ~~^~~~~~~~~~~
cake3.cpp:50:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   } else if (j == b.size()) {
      |              ~~^~~~~~~~~~~

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