oj.uz

Submission #394562

# Submission time Handle Problem Language Result Execution time Memory
394562 2021-04-26T21:33:58 Z rainboy Teams (IOI15_teams) C
100 / 100
 941 ms 136500 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 7 ms 448 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 22736 KB Output is correct
2 Correct 72 ms 22608 KB Output is correct
3 Correct 72 ms 22592 KB Output is correct
4 Correct 266 ms 23816 KB Output is correct
5 Correct 37 ms 22668 KB Output is correct
6 Correct 36 ms 22580 KB Output is correct
7 Correct 37 ms 22732 KB Output is correct
8 Correct 38 ms 22564 KB Output is correct
9 Correct 79 ms 22192 KB Output is correct
10 Correct 56 ms 22084 KB Output is correct
11 Correct 32 ms 21868 KB Output is correct
12 Correct 31 ms 21904 KB Output is correct
13 Correct 38 ms 22328 KB Output is correct
14 Correct 42 ms 22096 KB Output is correct
15 Correct 63 ms 22700 KB Output is correct
16 Correct 60 ms 22652 KB Output is correct
17 Correct 37 ms 22992 KB Output is correct
18 Correct 33 ms 22920 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 23024 KB Output is correct
2 Correct 179 ms 23068 KB Output is correct
3 Correct 184 ms 25896 KB Output is correct
4 Correct 265 ms 23816 KB Output is correct
5 Correct 137 ms 23124 KB Output is correct
6 Correct 134 ms 22976 KB Output is correct
7 Correct 154 ms 22980 KB Output is correct
8 Correct 139 ms 23012 KB Output is correct
9 Correct 79 ms 22212 KB Output is correct
10 Correct 180 ms 22308 KB Output is correct
11 Correct 148 ms 22212 KB Output is correct
12 Correct 127 ms 22212 KB Output is correct
13 Correct 136 ms 22800 KB Output is correct
14 Correct 189 ms 24424 KB Output is correct
15 Correct 120 ms 23248 KB Output is correct
16 Correct 120 ms 23124 KB Output is correct
17 Correct 101 ms 23440 KB Output is correct
18 Correct 105 ms 23548 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 787 ms 126016 KB Output is correct
2 Correct 783 ms 125976 KB Output is correct
3 Correct 879 ms 132000 KB Output is correct
4 Correct 941 ms 127688 KB Output is correct
5 Correct 487 ms 125980 KB Output is correct
6 Correct 483 ms 125976 KB Output is correct
7 Correct 518 ms 126020 KB Output is correct
8 Correct 493 ms 130884 KB Output is correct
9 Correct 486 ms 126276 KB Output is correct
10 Correct 489 ms 123540 KB Output is correct
11 Correct 423 ms 124356 KB Output is correct
12 Correct 402 ms 125408 KB Output is correct
13 Correct 678 ms 130376 KB Output is correct
14 Correct 906 ms 136500 KB Output is correct
15 Correct 556 ms 133536 KB Output is correct
16 Correct 548 ms 133428 KB Output is correct
17 Correct 357 ms 133120 KB Output is correct
18 Correct 347 ms 132960 KB Output is correct