#include <stdio.h>
#define N 200000
#define INF 0x7fffffff
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int zz[4 + N], ll[4 + N], rr[4 + N], aa[4 + N], bb[4 + N], u_, l_, r_;
int node(int a, int b) {
static int _ = 1;
zz[_] = rand_();
aa[_] = a, bb[_] = b;
return _++;
}
void split(int u, int a) {
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
if (aa[u] < a) {
split(rr[u], a);
rr[u] = l_, l_ = u;
} else {
split(ll[u], a);
ll[u] = r_, r_ = 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);
return u;
} else {
ll[v] = merge(u, ll[v]);
return v;
}
}
void floor_(int u, int a, int b, int *x, int *y) {
*x = *y = -1;
while (u)
if (aa[u] <= a && bb[u] <= b)
*x = aa[u], *y = bb[u], u = rr[u];
else
u = ll[u];
}
void ceil_(int u, int a, int b, int *x, int *y) {
*x = *y = INF;
while (u)
if (aa[u] >= a && bb[u] >= b)
*x = aa[u], *y = bb[u], u = ll[u];
else
u = rr[u];
}
int main() {
int n, q, u1, u2;
scanf("%d%d", &n, &q);
u1 = 0, u2 = merge(node(-1, 0), merge(node(n - 1, n), node(n * 2 - 1, n * 2)));
while (q--) {
static char s[2];
int a, b, tmp;
scanf("%s%d%d", s, &a, &b), a--, b--;
if (s[0] != 'Q') {
if (a > b)
tmp = a, a = b, b = tmp;
if (s[0] == 'A')
split(u1, a), u1 = merge(merge(l_, node(a, b)), r_);
else
split(u2, a), u2 = merge(merge(l_, node(a, b)), r_);
} else {
int la, ra, lb, rb, a1, a2, b1, b2, c, tmp, da;
floor_(u2, INF, a, &tmp, &la), ceil_(u2, a, -1, &ra, &tmp);
floor_(u2, INF, b, &tmp, &lb), ceil_(u2, b, -1, &rb, &tmp);
da = 0;
if (a < n && b < n) {
if (a < b)
da = la == lb && ra == rb;
else {
ceil_(u1, a, -1, &a1, &a2), floor_(u1, b, INF, &b1, &b2);
if (a1 <= ra && b1 >= lb) {
ceil_(u2, b2, -1, &c, &tmp);
da = c >= a2;
}
}
} else if (a >= n && b >= n) {
if (a > b)
da = la == lb && ra == rb;
else {
floor_(u1, INF, a, &a1, &a2), ceil_(u1, -1, b, &b1, &b2);
if (a2 >= la && b2 <= rb) {
ceil_(u2, a1, -1, &c, &tmp);
da = c >= b1;
}
}
} else if (a < n && b >= n) {
ceil_(u1, a, b, &a1, &a2);
da = a1 <= ra && a2 <= rb;
} else {
floor_(u1, b, a, &b1, &b2);
da = b2 >= la && b1 >= lb;
}
printf(da ? "DA\n" : "NE\n");
}
}
return 0;
}
Compilation message
mostovi.c: In function 'main':
mostovi.c:71:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d%d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~
mostovi.c:77:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
77 | scanf("%s%d%d", s, &a, &b), a--, b--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
217 ms |
2520 KB |
Output is correct |
| 8 |
Correct |
180 ms |
2500 KB |
Output is correct |
| 9 |
Correct |
194 ms |
2764 KB |
Output is correct |
| 10 |
Correct |
177 ms |
2776 KB |
Output is correct |
