Submission #405713

#	Time	Username	Problem	Language	Result	Execution time	Memory
405713		rainboy	Aliens (IOI16_aliens)	C11	100 / 100	181 ms	6588 KiB

aliens

#include "aliens_c.h"

#define N	100000
#define INF	0x3f3f3f3f3f3f3f3f

unsigned int X = 12345;

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

int aa[N], bb[N];

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) {
			int c = aa[ii[j]] != aa[i_] ? aa[ii[j]] - aa[i_] : bb[i_] - bb[ii[j]];

			if (c == 0)
				j++;
			else if (c < 0) {
				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;
	}
}

long long dp[N + 1], xx[N + 1], yy[N + 1]; int kk[N + 1];

long long cross(int i, int j, int k) {
	return (xx[j] - xx[i]) * (yy[k] - yy[i]) - (xx[k] - xx[i]) * (yy[j] - yy[i]);
}

long long dot(long long x1, long long y1, long long x2, long long y2) {
	return x1 * x2 + y1 * y2;
}

long long eval(int i, long long x) {
	return xx[i] * x - yy[i];
}

void solve(int *ii, int n, long long c) {
	static int qu[N + 1];
	int i, head, cnt;

	dp[0] = 0, kk[0] = 0;
	xx[0] = aa[ii[0]], yy[0] = dp[0] + (long long) aa[ii[0]] * aa[ii[0]];
	head = cnt = 0;
	qu[head + cnt++] = 0;
	for (i = 1; i <= n; i++) {
		int b = bb[ii[i - 1]];

		while (cnt >= 2 && eval(qu[head], b * 2) < eval(qu[head + 1], b * 2))
			head++, cnt--;
		dp[i] = -eval(qu[head], b * 2) + (long long) b * b + c, kk[i] = kk[qu[head]] + 1;
		if (i < n) {
			int a = aa[ii[i]];

			if (b > a)
				dp[i] -= (long long) (b - a) * (b - a);
			xx[i] = a, yy[i] = dp[i] + (long long) a * a;
			while (cnt >= 2 && cross(qu[head + cnt - 2], qu[head + cnt - 1], i) <= 0)
				cnt--;
			qu[head + cnt++] = i;
		}
	}
}

long long take_photos(int n, int m, int k, int *rr, int *cc) {
	static int ii[N];
	int n_, i;
	long long lower, upper;

	for (i = 0; i < n; i++) {
		int tmp;

		aa[i] = rr[i], bb[i] = cc[i];
		if (aa[i] > bb[i])
			tmp = aa[i], aa[i] = bb[i], bb[i] = tmp;
		bb[i]++;
		ii[i] = i;
	}
	sort(ii, 0, n);
	n_ = 0;
	for (i = 0; i < n; i++)
		if (n_ == 0 || bb[ii[n_ - 1]] < bb[ii[i]])
			ii[n_++] = ii[i];
	n = n_;
	lower = -1, upper = (long long) m * m + 1;
	while (upper - lower > 1) {
		long long c = (lower + upper) / 2;

		solve(ii, n, c);
		if (kk[n] <= k)
			upper = c;
		else
			lower = c;
	}
	solve(ii, n, upper);
	return dp[n] - upper * k;
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40