Submission #394562

#	Time	Username	Problem	Language	Result	Execution time	Memory
394562		rainboy	Teams (IOI15_teams)	C11	100 / 100	941 ms	136500 KiB

teams

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

#define N	500000
#define M	200000
#define LN	19	/* LN = ceil(log2(N)) */
#define N_	(N * (LN + 1))
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

unsigned int X = 12345;

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

int ii[N], tt[N + 1], n;

int *rr_;

int compare_r(int i, int j) { return rr_[i] - rr_[j]; }
int compare_k(int k1, int k2) { return k1 - k2; }

int (*compare)(int, int);

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 = compare(ii[j], i_);

			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;
	}
}

int ll[1 + N_], rr[1 + N_], sz[1 + N_], _ = 1;

int update(int t, int l, int r, int i) {
	int t_ = _++;

	sz[t_] = sz[t] + 1;
	if (r - l > 1) {
		int m = (l + r) / 2;

		if (i < m)
			ll[t_] = update(ll[t], l, m, i), rr[t_] = rr[t];
		else
			ll[t_] = ll[t], rr[t_] = update(rr[t], m, r, i);
	}
	return t_++;
}

int query(int t, int i) {
	int l = 0, r = n, x;

	x = 0;
	while (r - l > 1) {
		int m = (l + r) / 2;

		if (i < m)
			x += sz[rr[t]], t = ll[t], r = m;
		else
			t = rr[t], l = m;
	}
	if (i == -1)
		x += sz[t];
	return x;
}

void init(int n_, int ll[], int rr[]) {
	int h, i, t;

	n = n_;
	for (i = 0; i < n; i++)
		ii[i] = i;
	rr_ = rr, compare = compare_r, sort(ii, 0, n);
	for (h = 0, i = 0, t = 0; i <= n; i++) {
		while (h < n && rr[ii[h]] == i)
			t = update(t, 0, n, ll[ii[h++]] - 1);
		tt[i] = t;
	}
}

int dp[M + 2], kk[M], m;

int E(int i, int j) {
	int l = i == 0 ? -1 : kk[i - 1] - 1, r = j == m + 1 ? n : kk[j - 1] - 1;

	return dp[i] - query(tt[r], l);
}

int C(int i1, int i2) {
	int lower = i2, upper = m + 2;

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

		if (E(i1, j) <= E(i2, j))
			upper = j;
		else
			lower = j;
	}
	return upper;
}

int can(int m_, int *kk_) {
	static int qu[M + 2], cc[M + 2];
	int i, j, cnt;

	memcpy(kk, kk_, (m = m_) * sizeof *kk_);
	compare = compare_k, sort(kk, 0, m);
	cnt = 0;
	dp[0] = n, qu[cnt++] = 0;
	for (j = 1; j <= m + 1; j++) {
		while (cnt >= 2 && cc[cnt - 2] <= j)
			cnt--;
		dp[j] = E(qu[cnt - 1], j) - (j == m + 1 ? 0 : kk[j - 1]);
		while (cnt >= 2 && E(qu[cnt - 1], cc[cnt - 2] - 1) >= E(j, cc[cnt - 2] - 1))
			cnt--;
		qu[cnt] = j, cc[cnt - 1] = C(qu[cnt - 1], j), cnt++;
	}
	return dp[m + 1] >= 0;
}

Compilation message (stderr)

teams.c: In function 'rand_':
teams.c:15:18: warning: conversion to 'int' from 'unsigned int' may change the sign of the result [-Wsign-conversion]
   15 |  return (X *= 3) >> 1;
      |         ~~~~~~~~~^~~~
teams.c: In function 'sort':
teams.c:27:16: warning: declaration of 'ii' shadows a global declaration [-Wshadow]
   27 | void sort(int *ii, int l, int r) {
      |           ~~~~~^~
teams.c:18:5: note: shadowed declaration is here
   18 | int ii[N], tt[N + 1], n;
      |     ^~
teams.c: In function 'init':
teams.c:83:23: warning: declaration of 'll' shadows a global declaration [-Wshadow]
   83 | void init(int n_, int ll[], int rr[]) {
      |                   ~~~~^~~~
teams.c:49:5: note: shadowed declaration is here
   49 | int ll[1 + N_], rr[1 + N_], sz[1 + N_], _ = 1;
      |     ^~
teams.c:83:33: warning: declaration of 'rr' shadows a global declaration [-Wshadow]
   83 | void init(int n_, int ll[], int rr[]) {
      |                             ~~~~^~~~
teams.c:49:17: note: shadowed declaration is here
   49 | int ll[1 + N_], rr[1 + N_], sz[1 + N_], _ = 1;
      |                 ^~
teams.c: In function 'can':
teams.c:123:27: warning: conversion to 'long unsigned int' from 'int' may change the sign of the result [-Wsign-conversion]
  123 |  memcpy(kk, kk_, (m = m_) * sizeof *kk_);
      |                           ^
teams.c:121:6: warning: unused variable 'i' [-Wunused-variable]
  121 |  int i, j, cnt;
      |      ^

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23