Submission #395719

#	Time	Username	Problem	Language	Result	Execution time	Memory
395719		rainboy	Teams (IOI15_teams)	C11	100 / 100	1247 ms	208488 KiB

teams

/* https://codeforces.com/blog/entry/19454?#comment-243243 (zxqfl) */
#include "teams.h"

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

unsigned int X = 12345;

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

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

int *ll_;

int compare_l(int i, int j) { return ll_[i] - ll_[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_], cnt[1 + N_], _ = 1;

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

	cnt[t_] = cnt[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_;
}

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

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

int k_;

int update_(int t1, int t2, int l, int r, int i) {
	int m, t_;

	if (r <= i || k_ == 0)
		return t1;
	if (l >= i && k_ >= cnt[t2] - cnt[t1]) {
		k_ -= cnt[t2] - cnt[t1];
		return t2;
	}
	t_ = _++;
	m = (l + r) / 2;
	if (r - l > 1) {
		ll[t_] = update_(ll[t1], ll[t2], l, m, i), rr[t_] = update_(rr[t1], rr[t2], m, r, i);
		cnt[t_] = cnt[ll[t_]] + cnt[rr[t_]];
	} else
		cnt[t_] = cnt[t1] + k_, k_ = 0;
	return t_;
}

int can(int m, int *kk) {
	int i, t;

	compare = compare_k, sort(kk, 0, m);
	t = 0;
	for (i = 0; i < m; i++) {
		k_ = kk[i], t = update_(t, tt[kk[i]], 0, n, kk[i] - 1);
		if (k_ > 0)
			return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.c: In function 'rand_':
teams.c:13:18: warning: conversion to 'int' from 'unsigned int' may change the sign of the result [-Wsign-conversion]
   13 |  return (X *= 3) >> 1;
      |         ~~~~~~~~~^~~~
teams.c: In function 'sort':
teams.c:25:16: warning: declaration of 'ii' shadows a global declaration [-Wshadow]
   25 | void sort(int *ii, int l, int r) {
      |           ~~~~~^~
teams.c:16:5: note: shadowed declaration is here
   16 | int ii[N], tt[N + 1], n;
      |     ^~
teams.c: In function 'init':
teams.c:64:23: warning: declaration of 'll' shadows a global declaration [-Wshadow]
   64 | void init(int n_, int ll[], int rr[]) {
      |                   ~~~~^~~~
teams.c:47:5: note: shadowed declaration is here
   47 | int ll[1 + N_], rr[1 + N_], cnt[1 + N_], _ = 1;
      |     ^~
teams.c:64:33: warning: declaration of 'rr' shadows a global declaration [-Wshadow]
   64 | void init(int n_, int ll[], int rr[]) {
      |                             ~~~~^~~~
teams.c:47:17: note: shadowed declaration is here
   47 | int ll[1 + N_], rr[1 + N_], cnt[1 + N_], _ = 1;
      |                 ^~

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