#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]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |