Submission #721278

#	Time	Username	Problem	Language	Result	Execution time	Memory
721278		rainboy	Radio (Balkan15_RADIO)	C11	75 / 100	2041 ms	14752 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[N * 3];

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 zz[N * 3 + 1], ll[N * 3 + 1], rr[N * 3 + 1], ii_[N * 3 + 1], sz[N * 3 + 1], u_, l_, r_; long long ss[N * 3 + 1];

int node(int i) {
	static int _ = 1;

	zz[_] = rand_();
	ii_[_] = i;
	sz[_] = 1, ss[_] = cc[i];
	return _++;
}

void pul(int u) {
	int l = ll[u], r = rr[u];

	sz[u] = sz[l] + 1 + sz[r];
	ss[u] = ss[l] + cc[ii_[u]] + ss[r];
}

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = cc[ii_[u]] != cc[i] ? (cc[ii_[u]] < cc[i] ? -1 : 1) : ii_[u] - i;
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(v);
		return v;
	}
}

int tr_add(int u, int i) {
	split(u, i);
	return merge(merge(l_, node(i)), r_);
}

int tr_remove(int u, int i) {
	split(u, i);
	return merge(l_, r_);
}

int count(int u, long long c) {
	int k;

	k = 0;
	while (u)
		if (cc[ii_[u]] <= c)
			k += sz[u] - sz[rr[u]], u = rr[u];
		else
			u = ll[u];
	return k;
}

long long sum(int u, long long c) {
	long long s;

	s = 0;
	while (u)
		if (cc[ii_[u]] <= c)
			s += ss[u] - ss[rr[u]], u = rr[u];
		else
			u = ll[u];
	return s;
}

int main() {
	static int ww[N], ii[N * 2];
	int n, k, h, i, i_, ul, um, ur, 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[i * 3 + 0] = ww[i] + xx[i << 1 | 0];
		cc[i * 3 + 1] = ww[i];
		cc[i * 3 + 2] = ww[i] - xx[i << 1 | 1];
	}
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	sort(ii, 0, n * 2);
	ul = 0, um = 0, ur = 0;
	for (i = 0; i < n; i++)
		ur = tr_add(ur, i * 3 + 0);
	ans = INF;
	for (h = 0; h < n * 2; h++) {
		i_ = ii[h], i = i_ >> 1, x = xx[i_];
		if ((i_ & 1) == 0) {
			ur = tr_remove(ur, i * 3 + 0);
			um = tr_add(um, i * 3 + 1);
		} else {
			um = tr_remove(um, i * 3 + 1);
			ul = tr_add(ul, i * 3 + 2);
		}
		lower = -1, upper = (long long) X * 4 + 1;
		while (upper - lower > 1) {
			c = (lower + upper) / 2;
			if (count(ul, c - x) + count(um, c) + count(ur, c + x) <= k)
				lower = c;
			else
				upper = c;
		}
		c = lower;
		kl = count(ul, c - x), km = count(um, c), kr = count(ur, c + x);
		ans = min(ans, sum(ul, c - x) + (long long) x * kl + sum(um, c) + sum(ur, 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:128:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
radio.c:133:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   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: 0 / 25