#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) {
int l = ql[a[i]], r = qr[a[i]];
if (r < m) pus(&al, &ao, 0, a[i]);
else if (l > m) pus(&ar, &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 (ii[i] + 1 < eo[i] && 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 > m ? opt : N + 1;
}
sz = 0;
for (int i = m; i <= y; ++i) {
while (eh_[i][ii_[i] - 1] > m) --ii_[i];
int opt = eh_[i][ii_[i] - 1], ll = eh_[i][ii_[i]];
for (; sz && stk[sz] >= ll - 1; --sz)
if (opt < closeR[stk[sz]])
opt = closeR[stk[sz]];
stk[++sz] = i;
closeR[i] = opt < m ? opt : 0;
}
dnc(m + 1, y, ar, ao_);
free(ar);
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;
}
}
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),
ii_[i] = eo_[i] - 1;
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:68:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d%d%d", &n, &m, &q);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
curtains.c:70:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d%d", &l, &r),
| ^~~~~~~~~~~~~~~~~~~~~
curtains.c:84:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d%d", ql + i, qr + i), I[i] = i;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
