Submission #204944

#	Time	Username	Problem	Language	Result	Execution time	Memory
204944		ics0503	Cake 3 (JOI19_cake3)	C++17	100 / 100	3608 ms	23652 KiB

cake3

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
long long n, m, allSum = 0;
multiset<long long >L, R; // R is big
void balance() {
	if (L.size() == 0 || R.size() == 0)return;
	if (R.size() < m) {
		long long lmax = (*L.rbegin());
		L.erase(L.find(lmax)); R.insert(lmax);
		allSum += lmax;
		return;
	}
	long long lmax = (*L.rbegin()), rmin = (*R.begin());
	if (lmax > rmin) {
		L.erase(L.find(lmax)); R.erase(R.find(rmin));
		L.insert(rmin); R.insert(lmax);
		allSum += lmax - rmin;
	}
}
void add(long long x) {
	if (R.size() < m) { R.insert(x); allSum += x; }
	else L.insert(x);
	balance();
}
void del(long long x) {
	if (L.find(x) != L.end())L.erase(L.find(x));
	else { R.erase(R.find(x)); allSum -= x; }
	balance();
}
struct vc { long long v, c; }a[212121];
bool sort_c(vc a, vc b) {
	if (a.c != b.c)return a.c < b.c;
	return a.v < b.v;
}
struct qr { long long s, e, p, q; };
long long get_ans() {
	vector<qr>Q, nxtQ;
	long long ans = -1e18;
	Q.push_back({ m - 1, n - 1, 0, n - 1  });
	while (!Q.empty()) {
		long long l = n, r = n-1;
		for (qr Q : Q) {
			long long s = Q.s, e = Q.e, p = Q.p, q = Q.q;
			if (s > e)continue;
			long long mid = (s + e) / 2, pv;
			while (mid - m + 1 < l || q < l) { l--; add(a[l].v); }
			while (mid < r) { del(a[r].v); r--; }
			long long res = allSum - 2 * (a[r].c - a[l].c); pv = l;
			ans = max(ans, res);
			while (p < l) {
				l--; add(a[l].v);
				long long RES = allSum - 2 * (a[r].c - a[l].c);
				if (res < RES)res = RES, pv = l;
				ans = max(ans, res);
			}
			nxtQ.push_back({ mid + 1, e,pv, q });
			nxtQ.push_back({ s, mid - 1 ,p, pv });
		}
		L.clear(); R.clear(); allSum = 0;
		Q.clear();
		for (qr q : nxtQ)Q.push_back(q);
		nxtQ.clear();
	}
	return ans;
}

int main() {
	long long i, j; scanf("%lld%lld", &n, &m);
	for (i = 0; i < n; i++) scanf("%lld%lld", &a[i].v, &a[i].c);
	sort(a, a + n, sort_c);
	printf("%lld", get_ans());
	return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void balance()':
cake3.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (R.size() < m) {
      ~~~~~~~~~^~~
cake3.cpp: In function 'void add(long long int)':
cake3.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (R.size() < m) { R.insert(x); allSum += x; }
      ~~~~~~~~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:71:15: warning: unused variable 'j' [-Wunused-variable]
  long long i, j; scanf("%lld%lld", &n, &m);
               ^
cake3.cpp:71:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long i, j; scanf("%lld%lld", &n, &m);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~
cake3.cpp:72:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < n; i++) scanf("%lld%lld", &a[i].v, &a[i].c);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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