Submission #377759

#	Time	Username	Problem	Language	Result	Execution time	Memory
377759		rainboy	Palembang Bridges (APIO15_bridge)	C11	100 / 100	736 ms	11500 KiB

bridge

#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 X = 12345;

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

int *aa;

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 (aa[ii[j]] == aa[i_])
				j++;
			else if (aa[ii[j]] < aa[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 xx[N * 2];

int zz[1 + N * 2], ll[1 + N * 2], rr[1 + N * 2], ii[1 + N * 2], kk[1 + N * 2], _, u_, l_, r_; long long sum[1 + N * 2];

int node(int i) {
	zz[_] = rand_(), ll[_] = rr[_] = 0;
	ii[_] = i, kk[_] = 1, sum[_] = xx[i];
	return _++;
}

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

	kk[u] = 1 + kk[l] + kk[r];
	sum[u] = xx[ii[u]] + sum[l] + sum[r];
}

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

	if (u == 0) {
		l_ = r_ = 0;
		return;
	}
	c = xx[ii[u]] != xx[i] ? xx[ii[u]] - xx[i] : ii[u] - i;
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	}
	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;
	}
}

long long query(int k) {
	int u;
	long long x;

	u = u_, x = 0;
	while (u) {
		int l = ll[u];

		if (k <= kk[l])
			u = l;
		else {
			k -= kk[l] + 1, x += sum[l] + xx[ii[u]];
			u = rr[u];
		}
	}
	return x;
}

void tr_add(int i) {
	split(u_, i);
	u_ = merge(merge(l_, node(i)), r_);
}

int main() {
	static int ii[N * 2], xx_[N];
	static long long pp[N + 1], qq[N + 1];
	int k, n, n_, i;
	long long ans, mn;

	scanf("%d%d", &k, &n);
	ans = 0, n_ = 0;
	for (i = 0; i < n; i++) {
		static char s[2], t[2];
		int l, r, tmp;

		scanf("%s%d%s%d", s, &l, t, &r);
		if (l > r)
			tmp = l, l = r, r = tmp;
		if (s[0] == t[0]) {
			ans += r - l;
			continue;
		}
		xx[n_ << 1 | 0] = l, xx[n_ << 1 | 1] = r, n_++;
	}
	n = n_;
	ans += n;
	if (k == 1) {
		for (i = 0; i < n * 2; i++)
			ii[i] = i;
		aa = xx, sort(ii, 0, n * 2);
		for (i = 0; i < n * 2; i++)
			ans += xx[ii[i]] * (i < n ? -1 : 1);
	} else {
		for (i = 0; i < n; i++) {
			xx_[i] = xx[i << 1 | 0] + xx[i << 1 | 1];
			ii[i] = i;
		}
		aa = xx_, sort(ii, 0, n);
		_ = 1, u_ = 0;
		for (i = 0; i <= n; i++) {
			pp[i] = sum[u_] - query(i) * 2;
			if (i < n)
				tr_add(ii[i] << 1 | 0), tr_add(ii[i] << 1 | 1);
		}
		_ = 1, u_ = 0;
		for (i = n; i >= 0; i--) {
			if (i < n)
				tr_add(ii[i] << 1 | 0), tr_add(ii[i] << 1 | 1);
			qq[i] = sum[u_] - query(n - i) * 2;
		}
		mn = INF;
		for (i = 0; i <= n; i++)
			mn = min(mn, pp[i] + qq[i]);
		ans += mn;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

bridge.c: In function 'main':
bridge.c:113:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  113 |  scanf("%d%d", &k, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~
bridge.c:119:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  119 |   scanf("%s%d%s%d", s, &l, t, &r);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37