oj.uz

Submission #73330

# Submission time Handle Problem Language Result Execution time Memory
73330 2018-08-28T07:28:42 Z 윤교준(#2271) Radio (Balkan15_RADIO) C++11
100 / 100
 163 ms 9896 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ_P;
typedef priority_queue<int, vector<int>, greater<int>> PQ_M;
static unsigned char str[5500055], *p=str;

const bool debug = 0;
const int MAXN = 100005;

struct EVT {
	EVT(int x, int idx) : x(x), idx(idx) {}
	int x, idx;

	bool operator < (const EVT &t) const {
		if(x != t.x) return x < t.x;
		return idx < t.idx;
	}
};

PQ_M AI, BI, CI, EAI, EBI, ECI;
PQ_P AO, BO, CO, EAO, EBO, ECO;

vector<EVT> EV;
vector<int> XV;

int A[MAXN], B[MAXN], C[MAXN];

ll Ans = INFLL, Sum, SumA, SumC;
int N, K;

inline void prop_M(PQ_M &A, PQ_M &EA) {
	for(; !EA.empty() && !A.empty();) {
		if(A.top() != EA.top()) break;
		A.pop();
		EA.pop();
	}
}
inline void prop_P(PQ_P &B, PQ_P &EB) {
	for(; !EB.empty() && !B.empty();) {
		if(B.top() != EB.top()) break;
		B.pop();
		EB.pop();
	}
}

inline void erase(PQ_M &A, PQ_P &B, PQ_M &EA, PQ_P &EB, int x) {
	prop_M(A, EA); prop_P(B, EB);
	if(!A.empty() && A.top() <= x) {
		if(A.top() == x) A.pop();
		else EA.push(x);
		Sum -= x;
		return;
	}
	if(B.top() == x) B.pop();
	else EB.push(x);
}
inline void goup(PQ_M &A, PQ_P &B, PQ_M &EA, PQ_P &EB) {
	for(int t;;) {
		prop_M(A, EA); prop_P(B, EB);
		if(B.empty()) break;
		t = B.top();
		if(A.empty() || t <= A.top()) break;
		B.pop();
		A.push(t);
		Sum += t;
	}
}
inline void goup(PQ_M &A, PQ_P &B, PQ_M &EA, PQ_P &EB, ll cut, ll dx) {
	for(ll x;;) {
		prop_P(B, EB);
		if(B.empty()) break;
		x = ll(B.top()) + dx;
		if(x <= cut) break;
		x -= dx;
		B.pop();
		A.push(x);
		Sum += x;
	}
}

void f(int X) {
	prop_P(AO, EAO);
	prop_P(BO, EBO);
	prop_P(CO, ECO);
	ll at = (AO.empty() ? -INFLL : AO.top()) + X;
	ll bt = BO.empty() ? -INFLL : BO.top();
	ll ct = (CO.empty() ? -INFLL : CO.top()) - X;
	ll mxt = max({at, bt, ct});
	if(mxt == at) {
		at -= X;
		AI.push(at);
		AO.pop();
		Sum += at;
	} else if(mxt == bt) {
		BI.push(bt);
		BO.pop();
		Sum += bt;
	} else {
		ct += X;
		CI.push(ct);
		CO.pop();
		Sum += ct;
	}
}
void g(int X) {
	for(;;) {
		prop_M(AI, EAI); prop_P(AO, EAO);
		prop_M(BI, EBI); prop_P(BO, EBO);
		prop_M(CI, ECI); prop_P(CO, ECO);

		ll at = (AI.empty() ? INFLL : AI.top()) + X;
		ll bt = BI.empty() ? INFLL : BI.top();
		ll ct = (CI.empty() ? INFLL : CI.top()) - X;
		ll mnt = min({at, bt, ct});

		ll au = (AO.empty() ? -INFLL : AO.top()) + X;
		ll bu = BO.empty() ? -INFLL : BO.top();
		ll cu = (CO.empty() ? -INFLL : CO.top()) - X;
		ll mxu = max({au, bu, cu});

		if(mxu <= mnt) break;

		if(mnt == at) {
			at -= X;
			AI.pop();
			AO.push(at);
			Sum -= at;
		} else if(mnt == bt) {
			BI.pop();
			BO.push(bt);
			Sum -= bt;
		} else {
			ct += X;
			CI.pop();
			CO.push(ct);
			Sum -= ct;
		}

		if(mxu == au) {
			au -= X;
			AO.pop();
			AI.push(au);
			Sum += au;
		} else if(mxu == bu) {
			BO.pop();
			BI.push(bu);
			Sum += bu;
		} else {
			cu += X;
			CO.pop();
			CI.push(cu);
			Sum += cu;
		}
	}
}
void h(int X) {
	prop_M(AI, EAI);
	prop_M(BI, EBI);
	prop_M(CI, ECI);
	ll at = (AI.empty() ? INFLL : AI.top()) + X;
	ll bt = BI.empty() ? INFLL : BI.top();
	ll ct = (CI.empty() ? INFLL : CI.top()) - X;
	ll mnt = min({at, bt, ct});
	if(mnt == at) {
		at -= X;
		AI.pop();
		AO.push(at);
		Sum -= at;
	} else if(mnt == bt) {
		BI.pop();
		BO.push(bt);
		Sum -= bt;
	} else {
		ct += X;
		CI.pop();
		CO.push(ct);
		Sum -= ct;
	}
}

int main() {
	fread(str, 1, 5500055, stdin);

	rf(N) rf(K) K = N-K;
	for(int i = 1; i <= N; i++) { rf(A[i]) rf(B[i]) rf(C[i]) }

	XV.eb(-INF); XV.eb(INF);
	for(int i = 1; i <= N; i++) {
		XV.eb(A[i] - B[i]);
		XV.eb(A[i] + B[i]);
		EV.eb(A[i]-B[i], -i);
		EV.eb(A[i]+B[i], i);
	}
	sorv(XV); univ(XV);
	sorv(EV);

	if(debug) {
		for(int i = 1; i <= N; i++) printf("%d ; %d %d %d\n", i, A[i], B[i], C[i]);
		printf("XV : "); for(int v : XV) printf("%d ", v); puts("");
		printf("EV : "); for(auto &v : EV) printf("(%d,%d) ", v.x, v.idx); puts("");
		puts("");
	}

	for(int i = 1; i <= N; i++) {
		CO.push(A[i]-B[i]+C[i]);
		SumC += A[i]-B[i];
	}
	for(int xvi = 0, evi = 0, xvn = sz(XV), evn = sz(EV); xvi < xvn; xvi++) {
		const int X = XV[xvi];
		for(int idx, t; evi < evn && EV[evi].x <= X; evi++) {
			idx = EV[evi].idx;
			if(idx < 0) {
				idx = -idx;
				t = A[idx]-B[idx]+C[idx];
				erase(CI, CO, ECI, ECO, t);
				t = C[idx];
				BO.push(t);
				SumC -= A[idx]-B[idx];
			} else {
				t = C[idx];
				erase(BI, BO, EBI, EBO, t);
				t = -A[idx]-B[idx]+C[idx];
				AO.push(t);
				SumA += -A[idx]-B[idx];
			}
		}
		goup(AI, AO, EAI, EAO);
		goup(BI, BO, EBI, EBO);
		goup(CI, CO, ECI, ECO);
		for(int cnt = sz(AI) + sz(BI) + sz(CI) - sz(EAI) - sz(EBI) - sz(ECI); cnt < K; cnt++) f(X);
		for(int cnt = sz(AI) + sz(BI) + sz(CI) - sz(EAI) - sz(EBI) - sz(ECI); K < cnt; cnt--) h(X);
		g(X);

		{
			ll ret = SumA + SumC - Sum;
			ret += ll(X) * (sz(AO) - sz(EAO));
			ret -= ll(X) * (sz(CO) - sz(ECO));
			if(ret < Ans) Ans = ret;

			if(debug) {
				printf("X = %d, xvi=%d, evi=%d :: ret=%lld, Sum=%lld\n", X, xvi, evi, ret, Sum);
			}
		}
	}

	cout << Ans << endl;
	return 0;
}

Compilation message

code1.cpp: In function 'int main()':
code1.cpp:198:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fread(str, 1, 5500055, stdin);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 252 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 544 KB Output is correct
7 Correct 2 ms 620 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 4 ms 620 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 620 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1132 KB Output is correct
2 Correct 23 ms 2400 KB Output is correct
3 Correct 53 ms 4696 KB Output is correct
4 Correct 114 ms 8148 KB Output is correct
5 Correct 97 ms 8148 KB Output is correct
6 Correct 140 ms 9896 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9896 KB Output is correct
2 Correct 24 ms 9896 KB Output is correct
3 Correct 38 ms 9896 KB Output is correct
4 Correct 74 ms 9896 KB Output is correct
5 Correct 61 ms 9896 KB Output is correct
6 Correct 106 ms 9896 KB Output is correct

Subtask #6
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9896 KB Output is correct
2 Correct 49 ms 9896 KB Output is correct
3 Correct 41 ms 9896 KB Output is correct
4 Correct 78 ms 9896 KB Output is correct
5 Correct 98 ms 9896 KB Output is correct
6 Correct 163 ms 9896 KB Output is correct
7 Correct 118 ms 9896 KB Output is correct
8 Correct 157 ms 9896 KB Output is correct
9 Correct 142 ms 9896 KB Output is correct
10 Correct 102 ms 9896 KB Output is correct