Submission #721300

#	Time	Username	Problem	Language	Result	Execution time	Memory
721300		rainboy	Radio (Balkan15_RADIO)	C11	45 / 100	2060 ms	10352 KiB

radio

#include <stdio.h>

#define N	100000
#define X	1000000000
#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], cc[3][N], cc_[3][N], hh[3][N], n;

int *vv;

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 (vv[ii[j]] == vv[i_])
				j++;
			else if (vv[ii[j]] < vv[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;
	}
}

void update(long long *ft, int i, int n, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

long long query(long long *ft, int i) {
	long long x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

long long ftk[3][N], fts[3][N];

int count(int g, long long c) {
	int lower = -1, upper = n;

	while (upper - lower > 1) {
		int h = (lower + upper) / 2;

		if (cc_[g][h] <= c)
			lower = h;
		else
			upper = h;
	}
	return query(ftk[g], lower);
}

long long sum(int g, long long c) {
	int lower = -1, upper = n;

	while (upper - lower > 1) {
		int h = (lower + upper) / 2;

		if (cc_[g][h] <= c)
			lower = h;
		else
			upper = h;
	}
	return query(fts[g], lower);
}

int main() {
	static int ww[N], ii[N * 2];
	int k, g, h, i, i_, x, kl, km, kr;
	long long w, lower, upper, c, 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];
		cc[2][i] = ww[i] + xx[i << 1 | 0];
	}
	for (g = 0; g < 3; g++) {
		for (i = 0; i < n; i++)
			ii[i] = i;
		vv = cc[g], sort(ii, 0, n);
		for (h = 0; h < n; h++) {
			i = ii[h];
			cc_[g][h] = cc[g][i];
			hh[g][i] = h;
		}
	}
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	vv = xx, sort(ii, 0, n * 2);
	for (i = 0; i < n; i++)
		update(ftk[2], hh[2][i], n, 1), update(fts[2], hh[2][i], n, cc_[2][hh[2][i]]);
	ans = INF;
	for (h = 0; h < n * 2; h++) {
		i_ = ii[h], i = i_ >> 1, x = xx[i_];
		if ((i_ & 1) == 0) {
			update(ftk[2], hh[2][i], n, -1), update(fts[2], hh[2][i], n, -cc_[2][hh[2][i]]);
			update(ftk[1], hh[1][i], n, 1), update(fts[1], hh[1][i], n, cc_[1][hh[1][i]]);
		} else {
			update(ftk[1], hh[1][i], n, -1), update(fts[1], hh[1][i], n, -cc_[1][hh[1][i]]);
			update(ftk[0], hh[0][i], n, 1), update(fts[0], hh[0][i], n, cc_[0][hh[0][i]]);
		}
		lower = -1, upper = (long long) X * 4 + 1;
		while (upper - lower > 1) {
			c = (lower + upper) / 2;
			if (count(0, c - x) + count(1, c) + count(2, c + x) <= k)
				lower = c;
			else
				upper = c;
		}
		c = lower;
		kl = count(0, c - x), km = count(1, c), kr = count(2, c + x);
		ans = min(ans, sum(0, c - x) + (long long) x * kl + sum(1, c) + sum(2, c + x) - (long long) x * kr + (c + 1) * (k - kl - km - kr) - w);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

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

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