#include <stdio.h>
#define N 200000
#define INF 0x3f3f3f3f
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;
}
}
int tr_lower(int u, int a) {
int a_ = -1;
while (u)
if (aa[u] < a)
a_ = aa[u], u = rr[u];
else
u = ll[u];
return a_;
}
int tr_ceil(int u, int a) {
int a_ = INF;
while (u)
if (aa[u] >= a)
a_ = aa[u], u = ll[u];
else
u = rr[u];
return a_;
}
int check(int u, int a, int b, int c, int d) {
while (u)
if (aa[u] < a || bb[u] < b)
u = rr[u];
else if (aa[u] > c || bb[u] > d)
u = ll[u];
else
return 1;
return 0;
}
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 {
if (a < n && b < n)
printf(a > b || tr_ceil(u2, a) < b ? "NE\n" : "DA\n");
else if (a >= n && b >= n)
printf(a < b || tr_lower(u2, a) >= b ? "NE\n" : "DA\n");
else if (a < n && b >= n)
printf(check(u1, a, b, tr_ceil(u2, a), tr_ceil(u2, b)) ? "DA\n" : "NE\n");
else
printf(check(u1, tr_lower(u2, b) + 1, tr_lower(u2, a) + 1, b, a) ? "DA\n" : "NE\n");
}
}
return 0;
}
Compilation message
mostovi.c: In function 'main':
mostovi.c:86:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf("%d%d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~
mostovi.c:92:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | scanf("%s%d%d", s, &a, &b), a--, b--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
3 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
4 |
Incorrect |
1 ms |
296 KB |
Output isn't correct |
5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Incorrect |
161 ms |
6996 KB |
Output isn't correct |
8 |
Incorrect |
147 ms |
6980 KB |
Output isn't correct |
9 |
Incorrect |
151 ms |
7260 KB |
Output isn't correct |
10 |
Incorrect |
148 ms |
7236 KB |
Output isn't correct |