Submission #73305

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
73305	2018-08-28T07:03:56 Z	윤교준(#2271)	Radio (Balkan15_RADIO)	C++11	45 / 100	2000 ms	3868 KB

radio

#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) {
	prop_M(A, EA); prop_P(B, 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) {
	prop_M(A, EA); prop_P(B, EB);
	for(ll x;;) {
		prop_M(A, EA); 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;
	}
}

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++) {
			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 = (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;
			}
		}
		{
			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 l = INFLL;
			if(!AI.empty()) upmin(l, ll(AI.top()) + X);
			if(!BI.empty()) upmin(l, ll(BI.top()));
			if(!CI.empty()) upmin(l, ll(CI.top()) - X);
			goup(AI, AO, EAI, EAO, l, X);
			goup(BI, BO, EBI, EBO, l, 0);
			goup(CI, CO, ECI, ECO, l, -X);
		}
		for(int cnt = sz(AI) + sz(BI) + sz(CI) - sz(EAI) - sz(EBI) - sz(ECI); K < cnt; cnt--) {
			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});
			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;
			}
		}

		{
			ll ret = Sum;
			ret += ll(X) * (sz(AI) - sz(EAI));
			ret -= ll(X) * (sz(CI) - sz(ECI));
			ll cost = SumA + SumC;
			cost += ll(X) * (sz(AI) + sz(AO) - sz(EAI) - sz(EAO));
			cost -= ll(X) * (sz(CI) + sz(CO) - sz(ECI) - sz(ECO));
			
			ret = cost - ret;
			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:100: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	2 ms	376 KB	Output is correct
2	Correct	3 ms	488 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	3 ms	552 KB	Output is correct
5	Correct	3 ms	552 KB	Output is correct
6	Correct	3 ms	572 KB	Output is correct
7	Correct	3 ms	572 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	572 KB	Output is correct
2	Correct	10 ms	608 KB	Output is correct
3	Correct	34 ms	756 KB	Output is correct
4	Correct	51 ms	756 KB	Output is correct
5	Correct	93 ms	756 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	756 KB	Output is correct
2	Correct	3 ms	756 KB	Output is correct
3	Correct	46 ms	756 KB	Output is correct
4	Correct	88 ms	756 KB	Output is correct
5	Correct	4 ms	756 KB	Output is correct
6	Correct	7 ms	756 KB	Output is correct