Submission #390274

#	Time	Username	Problem	Language	Result	Execution time	Memory
390274		rainboy	Robots (IOI13_robots)	C11	100 / 100	1501 ms	20884 KiB

robots

#include "robots.h"
#include <string.h>

#define N	50000
#define M	50000
#define N_	(1 << 16)	/* N_ = pow2(ceil(log2(M + 1))) */
#define K	1000000

long long max(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;
	}
}

long long sum[N_ * 2], pref[N_ * 2]; int n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	sum[i] = sum[l] + sum[r], pref[i] = max(pref[l], sum[l] + pref[r]);
}

void build(int *ss, int k, int t) {
	int h, i;

	memset(sum + n_, 0, n_ * sizeof *sum);
	for (h = 0; h < k; h++)
		sum[n_ + ss[h]]++;
	for (i = 0; i < n_; i++) {
		if (i > 0)
			sum[n_ + i] -= t;
		pref[n_ + i] = max(sum[n_ + i], 0);
	}
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void decr(int i) {
	i += n_;
	pref[i] = max(--sum[i], 0);
	while (i > 1)
		pul(i >>= 1);
}

int solve(int *xx, int *ii, int n, int *ww, int *ss, int *hh, int k, int t) {
	int h, i;

	build(ss, k, t);
	for (i = 0, h = 0; i <= n; i++) {
		int x = i == 0 ? 0 : xx[ii[i - 1]];

		while (h < k && ww[hh[h]] < x)
			decr(ss[hh[h++]]);
		if (pref[1] - (long long) (n - i) * t > 0)
			return 0;
	}
	return 1;
}

int putaway(int n, int m, int k, int xx[], int yy[], int ww[], int ss[]) {
	static int ii[N], jj[M], hh[K];
	int h, i, j, lower, upper;

	for (i = 0; i < n; i++)
		ii[i] = i;
	aa = xx, sort(ii, 0, n);
	for (j = 0; j < m; j++)
		jj[j] = j;
	aa = yy, sort(jj, 0, m);
	for (h = 0; h < k; h++)
		hh[h] = h;
	aa = ss, sort(hh, 0, k);
	for (h = 0, j = 0; h < k; h++) {
		while (j < m && yy[jj[j]] <= ss[hh[h]])
			j++;
		ss[hh[h]] = m - j;
	}
	aa = ww, sort(hh, 0, k);
	n_ = 1;
	while (n_ < m + 1)
		n_ <<= 1;
	lower = 0, upper = k + 1;
	while (upper - lower > 1) {
		int t = (lower + upper) / 2;

		if (solve(xx, ii, n, ww, ss, hh, k, t))
			upper = t;
		else
			lower = t;
	}
	return upper == k + 1 ? -1 : upper;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10