//InTheNameOfGOD
//PRS;)
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define rep(i, l, r, x) for(ll i = l; i != r; i += x)
#define max(x, y) (x > y ? x : y)
#define mx(x, y) (x = max(x, y))
#define X first
#define Y second
typedef int ll;
using namespace std;
typedef pair<ll, ll> pl;
ypedef pair<ll, pl> pi;
constexpr ll xn = 1e6 + 5e5, xq = 1e6 + 5;
ll m1[xn << 2], m2[xn << 2], z1[xn << 2], z2[xn << 2], in[xn], ax[xq], ay[xq], o[xq], o1[xq], gt, prs;
pi q[xn], q1[xn];
void bld(ll v, ll l, ll r, ll l1, ll r1)
{
if(r <= l1 || r1 <= l) return;
m1[v] = m2[v] = z1[v] = z2[v] = -1;
if(r - l < 2) return;
ll m = l + r >> 1;
bld(v << 1, l, m, l1, r1), bld(v << 1 | 1, m, r, l1, r1);
}
inline void p1(ll v)
{
ll x = m1[v << 1], y = m1[v << 1 | 1];
if(x >= 0) mx(q[x].Y.X, z1[v]), mx(z1[v << 1], z1[v]);
if(y >= 0) mx(q[y].Y.X, z1[v]), mx(z1[v << 1 | 1], z1[v]);
z1[v] = -1;
}
inline void p2(ll v)
{
ll x = m2[v << 1], y = m2[v << 1 | 1];
if(x >= 0) mx(q[x].Y.Y, z2[v]), mx(z2[v << 1], z2[v]);
if(y >= 0) mx(q[y].Y.Y, z2[v]), mx(z2[v << 1 | 1], z2[v]);
z2[v] = -1;
}
void g1(ll v, ll l, ll r, ll l1, ll r1)
{
if(r <= l1 || r1 <= l) return;
if(l1 <= l && r <= r1)
{
if(m1[v] < 0) return;
if(gt < 0 || q[m1[v]].Y.X < q[gt].Y.X) gt = m1[v];
return;
}
if(z1[v] >= 0) p1(v);
ll m = l + r >> 1;
g1(v << 1, l, m, l1, r1), g1(v << 1 | 1, m, r, l1, r1);
}
void g2(ll v, ll l, ll r, ll l1, ll r1)
{
if(r <= l1 || r1 <= l) return;
if(l1 <= l && r <= r1)
{
if(m2[v] < 0) return;
if(gt < 0 || q[m2[v]].Y.Y < q[gt].Y.Y) gt = m2[v];
return;
}
if(z2[v] >= 0) p2(v);
ll m = l + r >> 1;
g2(v << 1, l, m, l1, r1), g2(v << 1 | 1, m, r, l1, r1);
}
inline void d1(ll v)
{
ll x = m1[v << 1], y = m1[v << 1 | 1];
m1[v] = (x < 0 ? y : y < 0 ? x : q[x].Y.X < q[y].Y.X ? x : y);
}
inline void d2(ll v)
{
ll x = m2[v << 1], y = m2[v << 1 | 1];
m2[v] = (x < 0 ? y : y < 0 ? x : q[x].Y.Y < q[y].Y.Y ? x : y);
}
void pt1(ll v, ll l, ll r, ll x, bool f)
{
if(x < l || r <= x) return;
if(r - l < 2)
{
m1[v] = -1;
if(f) m1[v] = x;
return;
}
if(z1[v] >= 0) p1(v);
ll m = l + r >> 1;
pt1(v << 1, l, m, x, f), pt1(v << 1 | 1, m, r, x, f), d1(v);
}
void pt2(ll v, ll l, ll r, ll x, bool f)
{
if(x < l || r <= x) return;
if(r - l < 2)
{
m2[v] = -1;
if(f) m2[v] = x;
return;
}
if(z2[v] >= 0) p2(v);
ll m = l + r >> 1;
pt2(v << 1, l, m, x, f), pt2(v << 1 | 1, m, r, x, f), d2(v);
}
void up1(ll v, ll l, ll r, ll l1, ll r1, ll x)
{
if(r <= l1 || r1 <= l) return;
if(l1 <= l && r <= r1)
{
ll y = m1[v];
if(y >= 0) mx(q[y].Y.X, x), mx(z1[v], x);
return;
}
ll m = l + r >> 1;
up1(v << 1, l, m, l1, r1, x), up1(v << 1 | 1, m, r, l1, r1, x);
}
void up2(ll v, ll l, ll r, ll l1, ll r1, ll x)
{
if(r <= l1 || r1 <= l) return;
if(l1 <= l && r <= r1)
{
ll y = m2[v];
if(y >= 0) mx(q[y].Y.Y, x), mx(z2[v], x);
return;
}
ll m = l + r >> 1;
up2(v << 1, l, m, l1, r1, x), up2(v << 1 | 1, m, r, l1, r1, x);
}
void doj(ll l, ll r, ll d, ll x, ll y, ll n)
{
ll l1 = l, r1 = r;
if(r1 < l1) swap(l1, r1), l1++, r1++;
if(r1 <= l1) return;
bld(1, 0, prs, l1, r1);
ll a1 = l1, a2 = r1 - 1, r2 = 0, c2 = 0;
if(n > 0) r2 = c2 = 1;
if(n > 1) r2 = (n + 1) >> 1, c2 = n >> 1;
rep(i, l, r, d)
{
if(o[i] == 1)
{
ll a = in[q[i].X], b = q[i].Y.X;
if(a < -1) q1[a1] = q[i], o1[a1++] = 1;
else if(a < 0) q1[a2] = q[i], o1[a2--] = 1;
if(a >= 0) g1(1, 0, prs, a, a + 1), g2(1, 0, prs, a, a + 1);
ax[b] = q[a].Y.X, ay[b] = q[a].Y.Y;
}
if(o[i] == 2)
{
ll a = q[i].X;
if(r2 <= a)
{
if(r2 < a) q1[a2] = {a - r2, {0, 0}}, o1[a2--] = 2;
up1(1, 0, prs, l1, r1, x + n - a);
}
else
{
q1[a1] = q[i], o1[a1++] = 2;
while(1)
{
gt = -1, g2(1, 0, prs, l1, r1);
if(gt < 0 || q[gt].Y.Y > y + a) break;
pt1(1, 0, prs, gt, 0), pt2(1, 0, prs, gt, 0);
pi p = q[gt];
q1[a1] = {p.X, {x - a + n, p.Y.Y}}, o1[a1++] = 4, in[p.X] = -2;
}
}
}
if(o[i] == 3)
{
ll a = q[i].X;
if(c2 <= a)
{
if(c2 < a) q1[a1] = {a - c2, {0, 0}}, o1[a1++] = 3;
up2(1, 0, prs, l1, r1, y + n - a);
}
else
{
q1[a2] = q[i], o1[a2--] = 3;
while(1)
{
gt = -1, g1(1, 0, prs, l1, r1);
if(gt < 0 || q[gt].Y.X > x + a) break;
pt1(1, 0, prs, gt, 0), pt2(1, 0, prs, gt, 0);
pi p = q[gt];
q1[a2] = {p.X, {p.Y.X, y - a + n}}, o1[a2--] = 4, in[p.X] = -1;
}
}
}
if(o[i] == 4)
{
pi p = q[i];
if(p.Y.X > x + c2) q1[a1] = p, in[p.X] = -2, o1[a1++] = 4;
else if(p.Y.Y > y + r2) q1[a2] = p, in[p.X] = -1, o1[a2--] = 4;
else pt1(1, 0, prs, i, 1), pt2(1, 0, prs, i, 1);
}
}
rep(i, l, r, d)
{
q[i] = q1[i], o[i] = o1[i];
if(o[i] == 4) in[q[i].X] = i;
}
if(n < 2) doj(l1, a1, 1, x + 1, y, 0), doj(r1 - 1, a2, -1, x, y + 1, 0);
else doj(l1, a1, 1, x + c2, y, r2), doj(r1 - 1, a2, -1, x, y + r2, c2);
}
int main()
{
ll n, m, Q;
scanf("%d %d %d", &n, &m, &Q);
rep(i, 0, m, 1)
{
ll x, y;
scanf("%d %d", &x, &y), q[i] = {i, {x, y}}, in[i] = i, o[i] = 4;
}
ll cnt = m, ca = 0;
rep(i, m, m + Q, 1)
{
scanf("%d", &o[i]);
if(o[i] < 4) scanf("%d", &q[i].X);
else scanf("%d %d", &q[i].Y.X, &q[i].Y.Y), in[cnt] = i, q[i].X = cnt++;
if(o[i] == 1) q[i].X--, q[i].Y.X = ca++;
}
prs = m + Q, doj(0, prs, 1, 0, 0, n);
rep(i, 0, ca, 1) printf("%d %d\n", ax[i], ay[i]);
}
Compilation message
sweeping.cpp:13:1: error: 'ypedef' does not name a type
13 | ypedef pair<ll, pl> pi;
| ^~~~~~
sweeping.cpp:16:1: error: 'pi' does not name a type; did you mean 'pl'?
16 | pi q[xn], q1[xn];
| ^~
| pl
sweeping.cpp: In function 'void bld(ll, ll, ll, ll, ll)':
sweeping.cpp:22:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | ll m = l + r >> 1;
| ~~^~~
sweeping.cpp: In function 'void p1(ll)':
sweeping.cpp:28:19: error: 'q' was not declared in this scope
28 | if(x >= 0) mx(q[x].Y.X, z1[v]), mx(z1[v << 1], z1[v]);
| ^
sweeping.cpp:7:19: note: in definition of macro 'mx'
7 | #define mx(x, y) (x = max(x, y))
| ^
sweeping.cpp:29:19: error: 'q' was not declared in this scope
29 | if(y >= 0) mx(q[y].Y.X, z1[v]), mx(z1[v << 1 | 1], z1[v]);
| ^
sweeping.cpp:7:19: note: in definition of macro 'mx'
7 | #define mx(x, y) (x = max(x, y))
| ^
sweeping.cpp: In function 'void p2(ll)':
sweeping.cpp:35:19: error: 'q' was not declared in this scope
35 | if(x >= 0) mx(q[x].Y.Y, z2[v]), mx(z2[v << 1], z2[v]);
| ^
sweeping.cpp:7:19: note: in definition of macro 'mx'
7 | #define mx(x, y) (x = max(x, y))
| ^
sweeping.cpp:36:19: error: 'q' was not declared in this scope
36 | if(y >= 0) mx(q[y].Y.Y, z2[v]), mx(z2[v << 1 | 1], z2[v]);
| ^
sweeping.cpp:7:19: note: in definition of macro 'mx'
7 | #define mx(x, y) (x = max(x, y))
| ^
sweeping.cpp: In function 'void g1(ll, ll, ll, ll, ll)':
sweeping.cpp:45:22: error: 'q' was not declared in this scope
45 | if(gt < 0 || q[m1[v]].Y.X < q[gt].Y.X) gt = m1[v];
| ^
sweeping.cpp:49:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | ll m = l + r >> 1;
| ~~^~~
sweeping.cpp: In function 'void g2(ll, ll, ll, ll, ll)':
sweeping.cpp:58:22: error: 'q' was not declared in this scope
58 | if(gt < 0 || q[m2[v]].Y.Y < q[gt].Y.Y) gt = m2[v];
| ^
sweeping.cpp:62:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
62 | ll m = l + r >> 1;
| ~~^~~
sweeping.cpp: In function 'void d1(ll)':
sweeping.cpp:68:38: error: 'q' was not declared in this scope
68 | m1[v] = (x < 0 ? y : y < 0 ? x : q[x].Y.X < q[y].Y.X ? x : y);
| ^
sweeping.cpp: In function 'void d2(ll)':
sweeping.cpp:73:38: error: 'q' was not declared in this scope
73 | m2[v] = (x < 0 ? y : y < 0 ? x : q[x].Y.Y < q[y].Y.Y ? x : y);
| ^
sweeping.cpp: In function 'void pt1(ll, ll, ll, ll, bool)':
sweeping.cpp:85:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | ll m = l + r >> 1;
| ~~^~~
sweeping.cpp: In function 'void pt2(ll, ll, ll, ll, bool)':
sweeping.cpp:98:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
98 | ll m = l + r >> 1;
| ~~^~~
sweeping.cpp: In function 'void up1(ll, ll, ll, ll, ll, ll)':
sweeping.cpp:107:23: error: 'q' was not declared in this scope
107 | if(y >= 0) mx(q[y].Y.X, x), mx(z1[v], x);
| ^
sweeping.cpp:7:19: note: in definition of macro 'mx'
7 | #define mx(x, y) (x = max(x, y))
| ^
sweeping.cpp:110:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
110 | ll m = l + r >> 1;
| ~~^~~
sweeping.cpp: In function 'void up2(ll, ll, ll, ll, ll, ll)':
sweeping.cpp:119:23: error: 'q' was not declared in this scope
119 | if(y >= 0) mx(q[y].Y.Y, x), mx(z2[v], x);
| ^
sweeping.cpp:7:19: note: in definition of macro 'mx'
7 | #define mx(x, y) (x = max(x, y))
| ^
sweeping.cpp:122:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
122 | ll m = l + r >> 1;
| ~~^~~
sweeping.cpp: In function 'void doj(ll, ll, ll, ll, ll, ll)':
sweeping.cpp:138:23: error: 'q' was not declared in this scope
138 | ll a = in[q[i].X], b = q[i].Y.X;
| ^
sweeping.cpp:139:24: error: 'q1' was not declared in this scope; did you mean 'a1'?
139 | if(a < -1) q1[a1] = q[i], o1[a1++] = 1;
| ^~
| a1
sweeping.cpp:140:28: error: 'q1' was not declared in this scope; did you mean 'a1'?
140 | else if(a < 0) q1[a2] = q[i], o1[a2--] = 1;
| ^~
| a1
sweeping.cpp:142:16: error: 'b' was not declared in this scope
142 | ax[b] = q[a].Y.X, ay[b] = q[a].Y.Y;
| ^
sweeping.cpp:146:20: error: 'q' was not declared in this scope
146 | ll a = q[i].X;
| ^
sweeping.cpp:149:28: error: 'q1' was not declared in this scope; did you mean 'a1'?
149 | if(r2 < a) q1[a2] = {a - r2, {0, 0}}, o1[a2--] = 2;
| ^~
| a1
sweeping.cpp:154:17: error: 'q1' was not declared in this scope; did you mean 'a1'?
154 | q1[a1] = q[i], o1[a1++] = 2;
| ^~
| a1
sweeping.cpp:160:21: error: 'pi' was not declared in this scope; did you mean 'i'?
160 | pi p = q[gt];
| ^~
| i
sweeping.cpp:161:31: error: 'p' was not declared in this scope
161 | q1[a1] = {p.X, {x - a + n, p.Y.Y}}, o1[a1++] = 4, in[p.X] = -2;
| ^
sweeping.cpp:167:20: error: 'q' was not declared in this scope
167 | ll a = q[i].X;
| ^
sweeping.cpp:170:28: error: 'q1' was not declared in this scope; did you mean 'a1'?
170 | if(c2 < a) q1[a1] = {a - c2, {0, 0}}, o1[a1++] = 3;
| ^~
| a1
sweeping.cpp:175:17: error: 'q1' was not declared in this scope; did you mean 'a1'?
175 | q1[a2] = q[i], o1[a2--] = 3;
| ^~
| a1
sweeping.cpp:181:21: error: 'pi' was not declared in this scope; did you mean 'i'?
181 | pi p = q[gt];
| ^~
| i
sweeping.cpp:182:31: error: 'p' was not declared in this scope
182 | q1[a2] = {p.X, {p.Y.X, y - a + n}}, o1[a2--] = 4, in[p.X] = -1;
| ^
sweeping.cpp:188:13: error: 'pi' was not declared in this scope; did you mean 'i'?
188 | pi p = q[i];
| ^~
| i
sweeping.cpp:189:16: error: 'p' was not declared in this scope
189 | if(p.Y.X > x + c2) q1[a1] = p, in[p.X] = -2, o1[a1++] = 4;
| ^
sweeping.cpp:189:32: error: 'q1' was not declared in this scope; did you mean 'a1'?
189 | if(p.Y.X > x + c2) q1[a1] = p, in[p.X] = -2, o1[a1++] = 4;
| ^~
| a1
sweeping.cpp:190:37: error: 'q1' was not declared in this scope; did you mean 'a1'?
190 | else if(p.Y.Y > y + r2) q1[a2] = p, in[p.X] = -1, o1[a2--] = 4;
| ^~
| a1
sweeping.cpp:196:9: error: 'q' was not declared in this scope
196 | q[i] = q1[i], o[i] = o1[i];
| ^
sweeping.cpp:196:16: error: 'q1' was not declared in this scope; did you mean 'a1'?
196 | q[i] = q1[i], o[i] = o1[i];
| ^~
| a1
sweeping.cpp: In function 'int main()':
sweeping.cpp:209:33: error: 'q' was not declared in this scope
209 | scanf("%d %d", &x, &y), q[i] = {i, {x, y}}, in[i] = i, o[i] = 4;
| ^
sweeping.cpp:215:35: error: 'q' was not declared in this scope
215 | if(o[i] < 4) scanf("%d", &q[i].X);
| ^
sweeping.cpp:216:30: error: 'q' was not declared in this scope
216 | else scanf("%d %d", &q[i].Y.X, &q[i].Y.Y), in[cnt] = i, q[i].X = cnt++;
| ^
sweeping.cpp:217:23: error: 'q' was not declared in this scope
217 | if(o[i] == 1) q[i].X--, q[i].Y.X = ca++;
| ^
sweeping.cpp:205:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
205 | scanf("%d %d %d", &n, &m, &Q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:214:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
214 | scanf("%d", &o[i]);
| ~~~~~^~~~~~~~~~~~~
