oj.uz

Submission #693304

# Submission time Handle Problem Language Result Execution time Memory
693304 2023-02-02T16:05:19 Z rainboy None (JOI16_matryoshka) C
26 / 100
 4 ms 468 KB 
#include <stdio.h>

#define N	200000
#define Q	200000
#define M	(N + Q)

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

unsigned int X = 12345;

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

int *uu, *vv;

void sort(int *gg, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, g = gg[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = uu[gg[j]] != uu[g] ? uu[gg[j]] - uu[g] : vv[gg[j]] - vv[g];

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = gg[i], gg[i] = gg[j], gg[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = gg[j], gg[j] = gg[k], gg[k] = tmp;
			}
		}
		sort(gg, l, i);
		l = k;
	}
}

int ft[M];

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

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

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

int main() {
	static int xx[M], yy[M], gg[M], ans[Q];
	int n, q, m, g, h, i, y;

	scanf("%d%d", &n, &q), m = n + q;
	for (g = 0; g < m; g++) {
		scanf("%d%d", &xx[g], &yy[g]);
		xx[g] = -xx[g];
	}
	for (g = 0; g < m; g++)
		gg[g] = g;
	uu = yy, vv = yy, sort(gg, 0, m);
	for (g = 0, y = 0; g < m; g++)
		yy[gg[g]] = g + 1 == m || yy[gg[g + 1]] != yy[gg[g]] ? y++ : y;
	uu = xx, vv = yy, sort(gg, 0, m);
	for (g = 0; g < m; g++)
		if (gg[g] < n) {
			i = gg[g];
			update(yy[i], m, query(yy[i]) + 1);
		} else {
			h = gg[g] - n;
			ans[h] = query(yy[n + h]);
		}
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h]);
	return 0;
}

Compilation message

matryoshka.c: In function 'main':
matryoshka.c:62:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d%d", &n, &q), m = n + q;
      |  ^~~~~~~~~~~~~~~~~~~~~
matryoshka.c:64:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d%d", &xx[g], &yy[g]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 300 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 300 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 2 ms 432 KB Output is correct
26 Correct 3 ms 364 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 3 ms 440 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Incorrect 2 ms 348 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 300 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 2 ms 432 KB Output is correct
26 Correct 3 ms 364 KB Output is correct
27 Correct 4 ms 340 KB Output is correct
28 Correct 3 ms 440 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Incorrect 2 ms 348 KB Output isn't correct
31 Halted 0 ms 0 KB -