제출 #114585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114585		tincamatei	Cake 3 (JOI19_cake3)	C++14	100 / 100	1370 ms	202656 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000;
const long long INF = 1LL << 60;

struct PersistentSegtree {
	int cnt;
	long long sum;
	PersistentSegtree *lT, *rT;

	PersistentSegtree() {
		cnt = 0;
		sum = 0LL;
		lT = rT = NULL;
	}
};

PersistentSegtree* build(int l, int r) {
	int mid = (l + r) / 2;
	PersistentSegtree* node = new PersistentSegtree();
	
	if(l < r) {
		node->lT = build(l, mid);
		node->rT = build(mid + 1, r);
	}
	
	return node;
}

PersistentSegtree* update(int poz, long long val, int l, int r, PersistentSegtree* nod) {
	if(poz < l || r < poz) return nod;
	PersistentSegtree* newnode = new PersistentSegtree();
	if(l == r) {
		newnode->cnt = nod->cnt + 1;
		newnode->sum = nod->sum + val;
	} else {
		int mid = (l + r) / 2;
		newnode->lT = update(poz, val, l, mid, nod->lT);
		newnode->rT = update(poz, val, mid + 1, r, nod->rT);
		newnode->cnt = newnode->lT->cnt + newnode->rT->cnt;
		newnode->sum = newnode->lT->sum + newnode->rT->sum;
	}

	return newnode;
}

long long query(int m, int l, int r, PersistentSegtree* minusTree, PersistentSegtree* plusTree) {
	if(l == r) {
		return plusTree->sum - minusTree->sum;
	} else {
		int leftCount = plusTree->lT->cnt - minusTree->lT->cnt, mid = (l + r) / 2;
		if(leftCount < m)
			return plusTree->lT->sum - minusTree->lT->sum +
			       query(m - leftCount, mid + 1, r, minusTree->rT, plusTree->rT);
		else
			return query(m, l, mid, minusTree->lT, plusTree->lT);
	}
}

struct Slice {
	int val, color, norm;
} slices[1+MAX_N];

bool colorSort(Slice a, Slice b) {
	return a.color < b.color;
}

bool valueSort(Slice a, Slice b) {
	return a.val < b.val;
}

long long solve(int l, int r, int cutL, int cutR, const int N, const int M, const vector<PersistentSegtree*> &versions) {
	int mid = (l + r) / 2, cut = cutL;
	long long rez = -INF;

	for(int i = cutL; i <= cutR && i <= mid - M + 1; ++i) {
		long long cost = query(M, 1, N, versions[i - 1], versions[mid]) - 2 * (slices[mid].color - slices[i].color);
		if(cost > rez) {
			rez = cost;
			cut = i;
		}
	}

	if(l < r) {
		rez = max(rez, solve(l, mid - 1, cutL, cut, N, M, versions));
		rez = max(rez, solve(mid + 1, r, cut, cutR, N, M, versions));
	}

	return rez;
}

int main() {
	int N, M;
	vector<PersistentSegtree*> versions;

	scanf("%d%d", &N, &M);
	for(int i = 1; i <= N; ++i)
		scanf("%d%d", &slices[i].val, &slices[i].color);
	
	sort(slices + 1, slices + 1 + N, valueSort);
	
	for(int i = 1; i <= N; ++i)
		slices[i].norm = N - i + 1;

	sort(slices + 1, slices + 1 + N, colorSort);
	
	versions.push_back(build(1, N));
	for(int i = 1; i <= N; ++i)
		versions.push_back(update(slices[i].norm, slices[i].val, 1, N, versions.back()));

	printf("%lld", solve(1, N, 1, N, N, M, versions));
	return 0;
} 

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In function 'int main()':
cake3.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
cake3.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &slices[i].val, &slices[i].color);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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