oj.uz

Submission #895296

# Submission time Handle Problem Language Result Execution time Memory
895296 2023-12-29T17:59:48 Z rainboy None (KOI18_matrix) C
38 / 100
 4000 ms 101588 KB 
#include <stdio.h>

#define M	3
#define N	200000
#define L	18	/* L = ceil(log2(N + 1)) */
#define N_	(1 << L)
#define N1	(N * (L + 1) + 1)

int max(int a, int b) { return a > b ? a : b; }

unsigned int Z = 12345;

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

int *xx_;

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 (xx_[ii[j]] == xx_[i_])
				j++;
			else if (xx_[ii[j]] < xx_[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;
	}
}

int ft[N];

void ft_update(int i, int n, int x) {
	while (i < n) {
		ft[i] = max(ft[i], x);
		i |= i + 1;
	}
}

int ft_query(int i) {
	int x = 0;

	while (i >= 0) {
		x = max(x, ft[i]);
		i &= i + 1, i--;
	}
	return x;
}

int zz[N1], ll[N1], rr[N1], yy[N1], xx[N1], mx[N1], l_, r_;

int node(int y, int x) {
	static int _ = 1;

	zz[_] = rand_();
	yy[_] = y, mx[_] = xx[_] = x;
	return _++;
}

void pul(int u) {
	mx[u] = max(xx[u], max(mx[ll[u]], mx[rr[u]]));
}

void split(int u, int y) {
	if (u == 0) {
		l_ = r_ = 0;
		return;
	}
	if (yy[u] < y) {
		split(rr[u], y);
		rr[u] = l_, l_ = u;
	} else if (yy[u] > y) {
		split(ll[u], y);
		ll[u] = r_, r_ = u;
	} else {
		l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(v);
		return v;
	}
}

int tr_update(int u, int y, int x) {
	split(u, y);
	return merge(merge(l_, node(y, x)), r_);
}

int tr_query(int u, int y) {
	int x = 0;

	while (u)
		if (yy[u] <= y)
			x = max(max(x, xx[u]), mx[ll[u]]), u = rr[u];
		else
			u = ll[u];
	return x;
}

int uu[N_ * 2], n_;

void st_update(int i, int y, int x) {
	for (i += n_; i > 0; i >>= 1)
		uu[i] = tr_update(uu[i], y, x);
}

int st_query(int r, int y) {
	int l = 0, x = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0)
			x = max(x, tr_query(uu[r--], y));
	return x;
}

int main() {
	static int ii[N], xx[M][N];
	int n, m, h, i, x, y;

	scanf("%d%d", &m, &n);
	for (h = 0; h < m; h++) {
		for (i = 0; i < n; i++)
			scanf("%d", &xx[h][i]);
		for (i = 0; i < n; i++)
			ii[i] = i;
		xx_ = xx[h], sort(ii, 0, n);
		for (i = 0; i < n; i++)
			xx[h][ii[i]] = i;
	}
	if (m == 2) {
		for (h = 0; h < n; h++) {
			x = xx[0][ii[h]];
			ft_update(x, n, ft_query(x) + 1);
		}
		printf("%d\n", ft_query(n - 1));
	} else {
		n_ = 1;
		while (n_ <= n)
			n_ <<= 1;
		for (h = 0; h < n; h++) {
			x = xx[0][ii[h]], y = xx[1][ii[h]];
			st_update(x, y, st_query(x, y) + 1);
		}
		printf("%d\n", st_query(n - 1, n - 1));
	}
	return 0;
}

Compilation message

matrix.c: In function 'main':
matrix.c:139:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |  scanf("%d%d", &m, &n);
      |  ^~~~~~~~~~~~~~~~~~~~~
matrix.c:142:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |    scanf("%d", &xx[h][i]);
      |    ^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2652 KB Output is correct
2 Correct 5 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2672 KB Output is correct
5 Correct 5 ms 2652 KB Output is correct
6 Correct 4 ms 2592 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 14164 KB Output is correct
2 Correct 25 ms 14248 KB Output is correct
3 Correct 37 ms 14332 KB Output is correct
4 Correct 47 ms 14168 KB Output is correct
5 Correct 32 ms 14172 KB Output is correct
6 Correct 18 ms 14168 KB Output is correct
7 Correct 43 ms 14160 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2652 KB Output is correct
2 Correct 5 ms 2652 KB Output is correct
3 Correct 4 ms 2652 KB Output is correct
4 Correct 4 ms 2672 KB Output is correct
5 Correct 5 ms 2652 KB Output is correct
6 Correct 4 ms 2592 KB Output is correct
7 Correct 4 ms 2652 KB Output is correct
8 Correct 93 ms 7244 KB Output is correct
9 Correct 99 ms 7332 KB Output is correct
10 Correct 93 ms 7188 KB Output is correct
11 Correct 95 ms 7248 KB Output is correct
12 Correct 93 ms 7332 KB Output is correct
13 Correct 91 ms 7296 KB Output is correct
14 Correct 93 ms 7256 KB Output is correct
15 Correct 93 ms 7508 KB Output is correct
16 Correct 91 ms 7408 KB Output is correct
17 Correct 90 ms 7188 KB Output is correct
18 Correct 93 ms 7260 KB Output is correct
19 Correct 94 ms 7276 KB Output is correct
20 Correct 96 ms 7224 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 14164 KB Output is correct
2 Correct 25 ms 14248 KB Output is correct
3 Correct 37 ms 14332 KB Output is correct
4 Correct 47 ms 14168 KB Output is correct
5 Correct 32 ms 14172 KB Output is correct
6 Correct 18 ms 14168 KB Output is correct
7 Correct 43 ms 14160 KB Output is correct
8 Correct 954 ms 101044 KB Output is correct
9 Correct 1529 ms 101132 KB Output is correct
10 Correct 719 ms 100948 KB Output is correct
11 Correct 553 ms 100948 KB Output is correct
12 Correct 3424 ms 101108 KB Output is correct
13 Correct 837 ms 101184 KB Output is correct
14 Correct 1395 ms 101588 KB Output is correct
15 Correct 638 ms 100816 KB Output is correct
16 Correct 624 ms 101020 KB Output is correct
17 Correct 1490 ms 101016 KB Output is correct
18 Execution timed out 4038 ms 92916 KB Time limit exceeded
19 Halted 0 ms 0 KB -