oj.uz

Submission #1111197

# Submission time Handle Problem Language Result Execution time Memory
1111197 2024-11-11T17:03:06 Z sleepntsheep Curtains (NOI23_curtains) C
100 / 100
 504 ms 76820 KB 
#include <stdio.h>
#include <stdlib.h>

#define N 500005

int n, m, q, *eh[N], eo[N], *eh_[N], eo_[N], ii[N], ii_[N], ans[N], I[N], qr[N], ql[N];

void pus(int **eh, int *eo, int i, int j) {
	int o = eo[i]++;
	if (!o) eh[i] = (int*)malloc(2 * sizeof **eh);
	else if (!(o & (o - 1))) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
	eh[i][o] = j;
}

int cmpr(const void *i, const void *j) {
	return *(const int*)i - *(const int*)j;
}

void dnc(int x, int y, int *a, int q) {
	if (x > y) 
		return;

	int *al = 0, *ar = 0, ao = 0, ao_ = 0, m = (x + y) / 2;
	for (int i = 0; i < q; ++i) 
		if (qr[a[i]] < m) 
			pus(&al, &ao, 0, a[i]);

	dnc(x, m - 1, al, ao);
	free(al);

	static int closeL[N], closeR[N], stk[N], sz;
	sz = 0;
	
	for (int i = m; i >= x; --i) {
		while (eh[i][ii[i] + 1] < m) ++ii[i];
		int opt = eh[i][ii[i] + 1], rr = eh[i][ii[i]];
		if (rr < m)
			for (; sz && stk[sz] <= rr + 1; --sz)
				if (opt > closeL[stk[sz]])
					opt = closeL[stk[sz]];
		stk[++sz] = i;
		closeL[i] = opt;
	}
	
	sz = 0;
	for (int i = m; i <= y; ++i) {
		while (eh_[i][ii_[i] + 1] <= m) ++ii_[i];
		int opt = eh_[i][ii_[i]], ll = eh_[i][ii_[i] + 1];
		if (ll > m)
			for (; sz && stk[sz] >= ll - 1; --sz)
				if (opt < closeR[stk[sz]])
					opt = closeR[stk[sz]];
		stk[++sz] = i;
		closeR[i] = opt;
	}

	for (int i = 0; i < q; ++i) {
		int l = ql[a[i]], r = qr[a[i]];
		if (l <= m && m <= r)
			ans[a[i]] = closeL[l] <= r && closeR[r] >= l;
		else if (l > m)
			pus(&ar, &ao_, 0, a[i]);
	}

	dnc(m + 1, y, ar, ao_);
	free(ar);
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	for (int i = m, l, r; i--;)
		scanf("%d%d", &l, &r),
		pus(eh, eo, l, r),
		pus(eh_, eo_, r, l);
	
	for (int i = 1; i <= n; ++i)
		pus(eh, eo, i, i - 1),
		pus(eh, eo, i, N + 1),
		pus(eh_, eo_, i, i + 1),
		pus(eh_, eo_, i, 0),
		qsort(eh[i], eo[i], sizeof **eh, cmpr),
		qsort(eh_[i], eo_[i], sizeof **eh_, cmpr);

	for (int i = 0; i < q; ++i)
		scanf("%d%d", ql + i, qr + i), I[i] = i;

	dnc(1, n, I, q);
	
	for (int i = 0; i < q; ++i)
		puts(ans[i]? "YES": "NO");
}

Compilation message

curtains.c: In function 'main':
curtains.c:70:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
curtains.c:72:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d%d", &l, &r),
      |   ^~~~~~~~~~~~~~~~~~~~~
curtains.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d%d", ql + i, qr + i), I[i] = i;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 2 ms 14672 KB Output is correct
4 Correct 2 ms 15000 KB Output is correct
5 Correct 2 ms 14764 KB Output is correct
6 Correct 2 ms 14844 KB Output is correct
7 Correct 2 ms 14832 KB Output is correct
8 Correct 2 ms 14840 KB Output is correct
9 Correct 2 ms 14672 KB Output is correct
10 Correct 2 ms 14672 KB Output is correct
11 Correct 2 ms 14672 KB Output is correct
12 Correct 2 ms 14672 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 2 ms 14672 KB Output is correct
4 Correct 2 ms 15000 KB Output is correct
5 Correct 2 ms 14764 KB Output is correct
6 Correct 2 ms 14844 KB Output is correct
7 Correct 2 ms 14832 KB Output is correct
8 Correct 2 ms 14840 KB Output is correct
9 Correct 2 ms 14672 KB Output is correct
10 Correct 2 ms 14672 KB Output is correct
11 Correct 2 ms 14672 KB Output is correct
12 Correct 2 ms 14672 KB Output is correct
13 Correct 4 ms 14928 KB Output is correct
14 Correct 4 ms 14928 KB Output is correct
15 Correct 4 ms 14928 KB Output is correct
16 Correct 4 ms 14928 KB Output is correct
17 Correct 4 ms 14928 KB Output is correct
18 Correct 3 ms 14928 KB Output is correct
19 Correct 3 ms 14932 KB Output is correct
20 Correct 4 ms 14928 KB Output is correct
21 Correct 4 ms 14928 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 2 ms 14672 KB Output is correct
4 Correct 2 ms 15000 KB Output is correct
5 Correct 2 ms 14764 KB Output is correct
6 Correct 2 ms 14844 KB Output is correct
7 Correct 2 ms 14832 KB Output is correct
8 Correct 2 ms 14840 KB Output is correct
9 Correct 2 ms 14672 KB Output is correct
10 Correct 2 ms 14672 KB Output is correct
11 Correct 2 ms 14672 KB Output is correct
12 Correct 2 ms 14672 KB Output is correct
13 Correct 4 ms 14928 KB Output is correct
14 Correct 4 ms 14928 KB Output is correct
15 Correct 4 ms 14928 KB Output is correct
16 Correct 4 ms 14928 KB Output is correct
17 Correct 4 ms 14928 KB Output is correct
18 Correct 3 ms 14928 KB Output is correct
19 Correct 3 ms 14932 KB Output is correct
20 Correct 4 ms 14928 KB Output is correct
21 Correct 4 ms 14928 KB Output is correct
22 Correct 89 ms 23136 KB Output is correct
23 Correct 82 ms 23596 KB Output is correct
24 Correct 105 ms 25700 KB Output is correct
25 Correct 196 ms 33944 KB Output is correct
26 Correct 84 ms 23524 KB Output is correct
27 Correct 209 ms 34056 KB Output is correct
28 Correct 194 ms 33952 KB Output is correct
29 Correct 77 ms 19712 KB Output is correct
30 Correct 72 ms 17744 KB Output is correct
31 Correct 83 ms 22956 KB Output is correct
32 Correct 206 ms 32288 KB Output is correct
33 Correct 74 ms 22048 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 2 ms 14672 KB Output is correct
4 Correct 2 ms 14672 KB Output is correct
5 Correct 3 ms 14928 KB Output is correct
6 Correct 3 ms 14928 KB Output is correct
7 Correct 4 ms 14928 KB Output is correct
8 Correct 75 ms 21792 KB Output is correct
9 Correct 89 ms 22928 KB Output is correct
10 Correct 202 ms 32184 KB Output is correct
11 Correct 76 ms 22040 KB Output is correct
12 Correct 61 ms 27820 KB Output is correct
13 Correct 56 ms 27788 KB Output is correct
14 Correct 62 ms 27628 KB Output is correct
15 Correct 62 ms 27680 KB Output is correct
16 Correct 62 ms 27676 KB Output is correct
17 Correct 70 ms 27700 KB Output is correct
18 Correct 393 ms 73872 KB Output is correct
19 Correct 358 ms 73612 KB Output is correct
20 Correct 426 ms 72936 KB Output is correct
21 Correct 501 ms 73144 KB Output is correct
22 Correct 463 ms 73232 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 2 ms 14672 KB Output is correct
4 Correct 2 ms 15000 KB Output is correct
5 Correct 2 ms 14764 KB Output is correct
6 Correct 2 ms 14844 KB Output is correct
7 Correct 2 ms 14832 KB Output is correct
8 Correct 2 ms 14840 KB Output is correct
9 Correct 2 ms 14672 KB Output is correct
10 Correct 2 ms 14672 KB Output is correct
11 Correct 2 ms 14672 KB Output is correct
12 Correct 2 ms 14672 KB Output is correct
13 Correct 4 ms 14928 KB Output is correct
14 Correct 4 ms 14928 KB Output is correct
15 Correct 4 ms 14928 KB Output is correct
16 Correct 4 ms 14928 KB Output is correct
17 Correct 4 ms 14928 KB Output is correct
18 Correct 3 ms 14928 KB Output is correct
19 Correct 3 ms 14932 KB Output is correct
20 Correct 4 ms 14928 KB Output is correct
21 Correct 4 ms 14928 KB Output is correct
22 Correct 42 ms 12624 KB Output is correct
23 Correct 42 ms 10648 KB Output is correct
24 Correct 68 ms 18264 KB Output is correct
25 Correct 64 ms 22872 KB Output is correct
26 Correct 60 ms 18208 KB Output is correct
27 Correct 63 ms 18196 KB Output is correct
28 Correct 68 ms 17364 KB Output is correct
29 Correct 60 ms 17996 KB Output is correct
30 Correct 77 ms 18248 KB Output is correct
31 Correct 65 ms 18504 KB Output is correct
32 Correct 83 ms 18360 KB Output is correct
33 Correct 101 ms 22880 KB Output is correct
34 Correct 67 ms 21356 KB Output is correct
35 Correct 67 ms 24576 KB Output is correct
36 Correct 63 ms 27888 KB Output is correct
37 Correct 59 ms 27784 KB Output is correct
38 Correct 64 ms 27728 KB Output is correct
39 Correct 87 ms 27680 KB Output is correct
40 Correct 89 ms 27660 KB Output is correct
41 Correct 85 ms 27504 KB Output is correct
42 Correct 66 ms 27680 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB Output is correct
2 Correct 2 ms 14672 KB Output is correct
3 Correct 2 ms 14672 KB Output is correct
4 Correct 2 ms 15000 KB Output is correct
5 Correct 2 ms 14764 KB Output is correct
6 Correct 2 ms 14844 KB Output is correct
7 Correct 2 ms 14832 KB Output is correct
8 Correct 2 ms 14840 KB Output is correct
9 Correct 2 ms 14672 KB Output is correct
10 Correct 2 ms 14672 KB Output is correct
11 Correct 2 ms 14672 KB Output is correct
12 Correct 2 ms 14672 KB Output is correct
13 Correct 4 ms 14928 KB Output is correct
14 Correct 4 ms 14928 KB Output is correct
15 Correct 4 ms 14928 KB Output is correct
16 Correct 4 ms 14928 KB Output is correct
17 Correct 4 ms 14928 KB Output is correct
18 Correct 3 ms 14928 KB Output is correct
19 Correct 3 ms 14932 KB Output is correct
20 Correct 4 ms 14928 KB Output is correct
21 Correct 4 ms 14928 KB Output is correct
22 Correct 89 ms 23136 KB Output is correct
23 Correct 82 ms 23596 KB Output is correct
24 Correct 105 ms 25700 KB Output is correct
25 Correct 196 ms 33944 KB Output is correct
26 Correct 84 ms 23524 KB Output is correct
27 Correct 209 ms 34056 KB Output is correct
28 Correct 194 ms 33952 KB Output is correct
29 Correct 77 ms 19712 KB Output is correct
30 Correct 72 ms 17744 KB Output is correct
31 Correct 83 ms 22956 KB Output is correct
32 Correct 206 ms 32288 KB Output is correct
33 Correct 74 ms 22048 KB Output is correct
34 Correct 2 ms 14672 KB Output is correct
35 Correct 2 ms 14672 KB Output is correct
36 Correct 2 ms 14672 KB Output is correct
37 Correct 2 ms 14672 KB Output is correct
38 Correct 3 ms 14928 KB Output is correct
39 Correct 3 ms 14928 KB Output is correct
40 Correct 4 ms 14928 KB Output is correct
41 Correct 75 ms 21792 KB Output is correct
42 Correct 89 ms 22928 KB Output is correct
43 Correct 202 ms 32184 KB Output is correct
44 Correct 76 ms 22040 KB Output is correct
45 Correct 61 ms 27820 KB Output is correct
46 Correct 56 ms 27788 KB Output is correct
47 Correct 62 ms 27628 KB Output is correct
48 Correct 62 ms 27680 KB Output is correct
49 Correct 62 ms 27676 KB Output is correct
50 Correct 70 ms 27700 KB Output is correct
51 Correct 393 ms 73872 KB Output is correct
52 Correct 358 ms 73612 KB Output is correct
53 Correct 426 ms 72936 KB Output is correct
54 Correct 501 ms 73144 KB Output is correct
55 Correct 463 ms 73232 KB Output is correct
56 Correct 42 ms 12624 KB Output is correct
57 Correct 42 ms 10648 KB Output is correct
58 Correct 68 ms 18264 KB Output is correct
59 Correct 64 ms 22872 KB Output is correct
60 Correct 60 ms 18208 KB Output is correct
61 Correct 63 ms 18196 KB Output is correct
62 Correct 68 ms 17364 KB Output is correct
63 Correct 60 ms 17996 KB Output is correct
64 Correct 77 ms 18248 KB Output is correct
65 Correct 65 ms 18504 KB Output is correct
66 Correct 83 ms 18360 KB Output is correct
67 Correct 101 ms 22880 KB Output is correct
68 Correct 67 ms 21356 KB Output is correct
69 Correct 67 ms 24576 KB Output is correct
70 Correct 63 ms 27888 KB Output is correct
71 Correct 59 ms 27784 KB Output is correct
72 Correct 64 ms 27728 KB Output is correct
73 Correct 87 ms 27680 KB Output is correct
74 Correct 89 ms 27660 KB Output is correct
75 Correct 85 ms 27504 KB Output is correct
76 Correct 66 ms 27680 KB Output is correct
77 Correct 450 ms 76820 KB Output is correct
78 Correct 431 ms 76636 KB Output is correct
79 Correct 359 ms 75816 KB Output is correct
80 Correct 452 ms 75908 KB Output is correct
81 Correct 373 ms 75128 KB Output is correct
82 Correct 362 ms 74716 KB Output is correct
83 Correct 385 ms 76632 KB Output is correct
84 Correct 406 ms 76252 KB Output is correct
85 Correct 504 ms 76496 KB Output is correct
86 Correct 461 ms 75908 KB Output is correct
87 Correct 381 ms 75820 KB Output is correct
88 Correct 365 ms 74620 KB Output is correct