Submission #721325

#	Time	Username	Problem	Language	Result	Execution time	Memory
721325		rainboy	Radio (Balkan15_RADIO)	C11	100 / 100	274 ms	8960 KiB

radio

#include <stdio.h>

#define N	100000
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int xx[N * 2], n, k;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int cc[6][N], iq[6][N + 1], pq[N], tt[N], cnt[6], t;

int lt(int i, int j) { return cc[t][i] < cc[t][j]; }

int p2(int p) {
	return (p *= 2) > cnt[t] ? 0 : (p < cnt[t] && lt(iq[t][p + 1], iq[t][p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[t][q]); p = q)
		iq[t][pq[j] = p] = j;
	iq[t][pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[t][q], i); p = q)
		iq[t][pq[j] = p] = j;
	iq[t][pq[i] = p] = i;
}

void pq_add(int i) {
	pq[i] = ++cnt[t], tt[i] = t, pq_up(i);
}

int pq_remove(int i) {
	int j = iq[t][cnt[t]--];

	if (j != i)
		pq[j] = pq[i], pq_up(j), pq_dn(j);
	pq[i] = 0, tt[i] = -1;
	return i;
}

long long sum; int x;

long long cost(int t, int i) {
	return (long long) cc[t][i] * ((t & 1) == 0 ? -1 : 1) + (1 - (t / 2)) * x;
}

void balance() {
	int t1, t2, i1, i1_, i2, i2_;
	long long c1, c1_, c2, c2_;

check:
	for (t1 = 0; t1 < 6; t1 += 2)
		for (t2 = 1; t2 < 6; t2 += 2)
			if (cnt[t1] && cnt[t2]) {
				i1 = iq[t1][1], i2 = iq[t2][1];
				if (cost(t1, i1) > cost(t2, i2)) {
					t = t1, pq_remove(i1), sum -= -cc[t1][i1];
					t = t1 ^ 1, pq_add(i1);
					t = t2, pq_remove(i2);
					t = t2 ^ 1, pq_add(i2), sum += -cc[t2 ^ 1][i2];
					goto check;
				}
			}
	while (cnt[0] + cnt[2] + cnt[4] < k) {
		c2_ = INF, i2_ = -1;
		for (t2 = 1; t2 < 6; t2 += 2)
			if (cnt[t2]) {
				i2 = iq[t2][1], c2 = cost(t2, i2);
				if (c2_ > c2)
					c2_ = c2, i2_ = i2;
			}
		i2 = i2_, t2 = tt[i2];
		t = t2, pq_remove(i2);
		t = t2 ^ 1, pq_add(i2), sum += -cc[t2 ^ 1][i2];
	}
	while (cnt[0] + cnt[2] + cnt[4] > k) {
		c1_ = -INF, i1_ = -1;
		for (t1 = 0; t1 < 6; t1 += 2)
			if (cnt[t1]) {
				i1 = iq[t1][1], c1 = cost(t1, i1);
				if (c1_ < c1)
					c1_ = c1, i1_ = i1;
			}
		i1 = i1_, t1 = tt[i1];
		t = t1, pq_remove(i1), sum -= -cc[t1][i1];
		t = t1 ^ 1, pq_add(i1);
	}
}

long long eval() {
	return sum + (long long) (cnt[0] - cnt[4]) * x;
}

int main() {
	static int ww[N], ii[N * 2];
	int h, i, i_;
	long long w, ans;

	scanf("%d%d", &n, &k);
	w = 0;
	for (i = 0; i < n; i++) {
		int p;

		scanf("%d%d%d", &x, &p, &ww[i]);
		w += ww[i];
		xx[i << 1 | 0] = x - p, xx[i << 1 | 1] = x + p;
		cc[0][i] = -(ww[i] - xx[i << 1 | 1]), cc[1][i] = ww[i] - xx[i << 1 | 1];
		cc[2][i] = -ww[i], cc[3][i] = ww[i];
		cc[4][i] = -(ww[i] + xx[i << 1 | 0]), cc[5][i] = ww[i] + xx[i << 1 | 0];
	}
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	sort(ii, 0, n * 2);
	for (i = 0; i < n; i++)
		t = 5, pq_add(i);
	ans = INF;
	for (h = 0; h < n * 2; h++) {
		i_ = ii[h], i = i_ >> 1, x = xx[i_];
		if ((i_ & 1) == 0) {
			t = tt[i], pq_remove(i);
			if ((t & 1) == 0)
				sum -= -cc[t][i];
			t = 3, pq_add(i);
		} else {
			t = tt[i], pq_remove(i);
			if ((t & 1) == 0)
				sum -= -cc[t][i];
			t = 1, pq_add(i);
		}
		balance();
		ans = min(ans, eval() - w);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

radio.c: In function 'main':
radio.c:130:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
radio.c:135:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |   scanf("%d%d%d", &x, &p, &ww[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 25 / 25