#include <stdio.h>
#include <string.h>
#define N 1500000
#define Q 1000000
#define LN 20 /* LN = ceil(log2(Q)) */
#define N_ (Q * (LN + 1) * 2 + 1)
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int n, q, s;
int tt[Q], ll[Q], rr[Q], xx_[Q], yy_[Q], zz[Q];
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)
if (zz[gg[j]] == zz[g])
j++;
else if (zz[gg[j]] < zz[g]) {
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 *hh_, ll_[N_], rr_[N_], xx1[N_], yy1[N_], xx2[N_], yy2[N_], _;
int node() {
ll_[_] = rr_[_] = 0;
return _++;
}
void pul(int t) {
if (t) {
int l = ll_[t], r = rr_[t];
xx1[t] = min(xx1[l], xx1[r]), xx2[t] = max(xx2[l], xx2[r]);
yy1[t] = min(yy1[l], yy1[r]), yy2[t] = max(yy2[l], yy2[r]);
}
}
int build(int l, int r) {
int t = node();
if (r - l > 1) {
int m = (l + r) / 2;
ll_[t] = build(l, m), rr_[t] = build(m, r), pul(t);
} else
xx1[t] = xx2[t] = xx_[hh_[l]], yy1[t] = yy2[t] = yy_[hh_[l]];
return t;
}
void split_x(int t, int x, int *t1, int *t2) {
if (t == 0)
*t1 = *t2 = 0;
else if (xx2[t] <= x)
*t1 = t, *t2 = 0;
else if (xx1[t] > x)
*t1 = 0, *t2 = t;
else {
int t1_, l1_, l2_, t2_, r1_, r2_;
split_x(ll_[t], x, &l1_, &l2_), split_x(rr_[t], x, &r1_, &r2_);
t1_ = t, t2_ = node();
ll_[t1_] = l1_, rr_[t1_] = r1_, pul(t1_);
ll_[t2_] = l2_, rr_[t2_] = r2_, pul(t2_);
*t1 = t1_, *t2 = t2_;
}
}
void split_y(int t, int y, int *t1, int *t2) {
if (t == 0)
*t1 = *t2 = 0;
else if (yy2[t] <= y)
*t1 = t, *t2 = 0;
else if (yy1[t] > y)
*t1 = 0, *t2 = t;
else {
int t1_, l1_, l2_, t2_, r1_, r2_;
split_y(ll_[t], y, &l1_, &l2_), split_y(rr_[t], y, &r1_, &r2_);
t1_ = t, t2_ = node();
if (l1_ || r1_)
ll_[t1_] = l1_, rr_[t1_] = r1_, pul(t1_);
else
t1_ = 0;
if (l2_ || r2_)
ll_[t2_] = l2_, rr_[t2_] = r2_, pul(t2_);
else
t2_ = 0;
*t1 = t1_, *t2 = t2_;
}
}
void print(int t, int l, int r, int x, int y) {
if (t == 0)
return;
if (r - l > 1) {
int m = (l + r) / 2;
print(ll_[t], l, m, x, y), print(rr_[t], m, r, x, y);
} else
xx_[hh_[l]] = max(xx_[hh_[l]], x), yy_[hh_[l]] = max(yy_[hh_[l]], y);
}
int gg[Q];
int ll1[N], rr1[N];
void dfs(int q, int g, int t, int x, int y) {
int g_, t1, t2;
if (g == -1)
print(t, 0, q, x, y);
else {
g_ = gg[g];
if (tt[g_] == 2) {
split_y(t, s - zz[g_], &t1, &t2);
dfs(q, ll1[g], t2, x, y), dfs(q, rr1[g], t1, max(x, zz[g_]), y);
} else if (tt[g_] == 3) {
split_x(t, zz[g_], &t1, &t2);
dfs(q, ll1[g], t1, x, max(y, s - zz[g_])), dfs(q, rr1[g], t2, x, y);
}
}
}
void solve_(int *hh, int q, int l, int r) {
static int qu[Q], pp[Q], qq[Q];
int m, g, g_, cnt;
m = 0;
for (g = l; g < r; g++)
if (tt[g] == 2 || tt[g] == 3)
gg[m++] = g;
if (q == 0 || m == 0)
return;
sort(gg, 0, m);
cnt = 0;
for (g = 0; g < m; g++) {
while (cnt && gg[qu[cnt - 1]] > gg[g])
cnt--;
pp[g] = cnt ? qu[cnt - 1] : m;
qu[cnt++] = g;
}
cnt = 0;
for (g = m - 1; g >= 0; g--) {
while (cnt && gg[qu[cnt - 1]] > gg[g])
cnt--;
qq[g] = cnt ? qu[cnt - 1] : m;
qu[cnt++] = g;
}
memset(ll1, -1, m * sizeof *ll1), memset(rr1, -1, m * sizeof *rr1);
g_ = -1;
for (g = 0; g < m; g++)
if (pp[g] == m && qq[g] == m)
g_ = g;
else if (qq[g] == m || pp[g] < m && gg[pp[g]] > gg[qq[g]])
rr1[pp[g]] = g;
else
ll1[qq[g]] = g;
hh_ = hh;
_ = 1, xx1[0] = INF, xx2[0] = -1, yy1[0] = INF, yy2[0] = -1;
dfs(q, g_, build(0, q), 0, 0);
}
void solve(int *hh, int q, int l, int r) {
int m, h1, h2, h3, tmp;
h1 = 0, h2 = 0, h3 = q;
while (h2 < h3)
if (ll[hh[h2]] <= l && r <= rr[hh[h2]])
h2++;
else if (ll[hh[h2]] < r && l < rr[hh[h2]]) {
tmp = hh[h1], hh[h1] = hh[h2], hh[h2] = tmp;
h1++, h2++;
} else {
h3--;
tmp = hh[h2], hh[h2] = hh[h3], hh[h3] = tmp;
}
solve_(hh + h1, h2 - h1, l, r);
if (r - l > 1) {
m = (l + r) / 2;
solve(hh, h1, l, m), solve(hh, h1, m, r);
}
}
int main() {
static int xx[N], yy[N], pp[N], hh[Q];
int m, h, i;
scanf("%d%d%d", &s, &n, &q);
for (i = 0; i < n; i++)
scanf("%d%d", &xx[i], &yy[i]);
memset(pp, -1, n * sizeof *pp);
for (h = 0; h < q; h++) {
scanf("%d", &tt[h]);
if (tt[h] == 1) {
scanf("%d", &i), i--;
ll[h] = pp[i] + 1, rr[h] = h, xx_[h] = xx[i], yy_[h] = yy[i];
} else if (tt[h] == 2 || tt[h] == 3) {
scanf("%d", &zz[h]);
if (tt[h] == 2)
zz[h] = s - zz[h];
} else
scanf("%d%d", &xx[n], &yy[n]), pp[n] = h, n++;
}
m = 0;
for (h = 0; h < q; h++)
if (tt[h] == 1)
hh[m++] = h;
solve(hh, m, 0, q);
for (h = 0; h < q; h++)
if (tt[h] == 1)
printf("%d %d\n", xx_[h], yy_[h]);
return 0;
}
Compilation message
sweeping.c: In function 'solve_':
sweeping.c:172:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
172 | else if (qq[g] == m || pp[g] < m && gg[pp[g]] > gg[qq[g]])
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.c: In function 'main':
sweeping.c:206:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
206 | scanf("%d%d%d", &s, &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.c:208:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
208 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.c:211:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
211 | scanf("%d", &tt[h]);
| ^~~~~~~~~~~~~~~~~~~
sweeping.c:213:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
213 | scanf("%d", &i), i--;
| ^~~~~~~~~~~~~~~
sweeping.c:216:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
216 | scanf("%d", &zz[h]);
| ^~~~~~~~~~~~~~~~~~~
sweeping.c:220:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
220 | scanf("%d%d", &xx[n], &yy[n]), pp[n] = h, n++;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
980 KB |
Output is correct |
| 2 |
Correct |
7 ms |
696 KB |
Output is correct |
| 3 |
Correct |
4 ms |
524 KB |
Output is correct |
| 4 |
Correct |
7 ms |
852 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3141 ms |
124088 KB |
Output is correct |
| 2 |
Correct |
3154 ms |
124548 KB |
Output is correct |
| 3 |
Correct |
3126 ms |
124488 KB |
Output is correct |
| 4 |
Correct |
1739 ms |
113944 KB |
Output is correct |
| 5 |
Correct |
1440 ms |
80844 KB |
Output is correct |
| 6 |
Correct |
1488 ms |
204300 KB |
Output is correct |
| 7 |
Correct |
3182 ms |
122756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2489 ms |
111060 KB |
Output is correct |
| 2 |
Correct |
2334 ms |
95492 KB |
Output is correct |
| 3 |
Correct |
2043 ms |
169580 KB |
Output is correct |
| 4 |
Correct |
1524 ms |
101800 KB |
Output is correct |
| 5 |
Incorrect |
2320 ms |
100016 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2489 ms |
111060 KB |
Output is correct |
| 2 |
Correct |
2334 ms |
95492 KB |
Output is correct |
| 3 |
Correct |
2043 ms |
169580 KB |
Output is correct |
| 4 |
Correct |
1524 ms |
101800 KB |
Output is correct |
| 5 |
Incorrect |
2320 ms |
100016 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
980 KB |
Output is correct |
| 2 |
Correct |
7 ms |
696 KB |
Output is correct |
| 3 |
Correct |
4 ms |
524 KB |
Output is correct |
| 4 |
Correct |
7 ms |
852 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
