#pragma gcc optimize("Ofast")
#pragma gcc optimize("O3")
#pragma gcc optimize("fast-math")
#pragma gcc target("avx,avx2,fma,sse,sse2,sse3,sse4,sse4.1,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
return y > x ? (x = y, true) : false;
}
void debug_out() {
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
cerr << ' ' << A;
debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
for (int i = 0; i < n; ++i)
cerr << a[i] << ' ';
cerr << endl;
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
for (auto& x : v)
stream << x << ' ';
return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
return stream << p.first << ' ' << p.second;
}
const int INF32 = 1e9;
const int maxN = 1.5e6 + 6;
const int maxQ = 1e6 + 6;
int L;
struct pt {
int x, y;
pt(int _x = 0, int _y = 0): x(_x), y(_y) {}
void read() {
cin >> x >> y;
}
} ans[maxQ], pos0[maxN];
namespace dsu {
const int maxV = 2 * maxN;
int q[maxV];
int val[maxV];
vector<int> vtx[maxV];
void new_node(int x, int v) {
q[x] = -1;
val[x] = v;
vtx[x] = {x};
}
int gt(int x) {
return q[x] < 0 ? x : q[x] = gt(q[x]);
}
int gval(int x) {
return val[gt(x)];
}
int join(int x, int y) {
// debug(x, y);
// debug(vtx[x]);
// debug(vtx[y]);
x = gt(x), y = gt(y);
if (x == y) return x;
if (-q[x] < -q[y]) swap(x, y);
q[x] += q[y];
q[y] = x;
for (int i : vtx[y])
vtx[x].push_back(i);
vtx[y].clear();
return x;
}
}
bool here[2 * maxN];
void solve(int stx, int sty, vector<array<int, 3>> que) {
if (que.empty()) return;
int L1 = L - stx - sty;
if (!L1) {
for (auto q : que) {
if (q[0] == 1) {
ans[q[2]] = {stx, sty};
}
}
return;
}
// debug(stx, sty);
// for (auto q : que)
// cerr << q[0] << ' ' << q[1] << ' ' << q[2] << endl;
int fnx = L - sty;
int fny = L - stx;
int midx = (stx + fnx) / 2;
int midy = (sty + fny) / 2;
vector<array<int, 3>> que_up, que_ri;
set<pii> px, py;
for (auto q : que) {
if (q[0] == 1) {
int i = q[1];
int t = q[2];
if (here[i]) {
ans[t].x = dsu::gval(i << 1);
ans[t].y = dsu::gval(i << 1 | 1);
} else if (pos0[i].x > midx) {
que_ri.push_back(q);
} else {
que_up.push_back(q);
}
} else if (q[0] == 2) { // H
int l = q[1];
if (l >= midy - sty) {
int x0 = stx + L1 - l;
int comp = -1;
while (!px.empty() && px.begin()->fi < x0) {
int c = px.begin()->se;
if (comp == -1)
comp = c;
else
comp = dsu::join(comp, c);
px.erase(px.begin());
}
if (comp != -1) {
dsu::val[comp] = x0;
px.insert({x0, comp});
}
if (l > midy - sty) {
q[1] -= (midy - sty + 1);
que_up.push_back(q);
}
} else {
int x0 = stx + L1 - l;
int y0 = sty + l;
while (!py.empty() && py.begin()->fi <= y0) {
int c = py.begin()->se;
for (int ii : dsu::vtx[c]) {
int i = ii / 2;
if (!here[i]) continue;
here[i] = false;
pos0[i].x = x0;
pos0[i].y = dsu::val[c];
array<int, 3> temp;
temp[0] = 4, temp[1] = i;
que_ri.push_back(temp);
}
py.erase(py.begin());
}
que_ri.push_back(q);
}
} else if (q[0] == 3) { // V
int l = q[1];
if (l >= midx - stx) {
int y0 = sty + L1 - l;
int comp = -1;
while (!py.empty() && py.begin()->fi < y0) {
int c = py.begin()->se;
if (comp == -1)
comp = c;
else
comp = dsu::join(comp, c);
py.erase(py.begin());
}
if (comp != -1) {
dsu::val[comp] = y0;
py.insert({y0, comp});
}
if (l > midx - stx) {
q[1] -= (midx - stx + 1);
que_ri.push_back(q);
}
} else {
int y0 = sty + L1 - l;
int x0 = stx + l;
while (!px.empty() && px.begin()->fi <= x0) {
int c = px.begin()->se;
for (int ii : dsu::vtx[c]) {
int i = ii / 2;
if (!here[i]) continue;
here[i] = false;
pos0[i].y = y0;
pos0[i].x = dsu::val[c];
array<int, 3> temp;
temp[0] = 4, temp[1] = i;
que_up.push_back(temp);
}
px.erase(px.begin());
}
que_up.push_back(q);
}
} else {
int i = q[1];
int x = pos0[i].x, y = pos0[i].y;
if (x <= midx && y <= midy) {
// debug(i,x,y);
here[i] = true;
px.insert({x, i << 1});
py.insert({y, i << 1 | 1});
dsu::new_node(i << 1, x);
dsu::new_node(i << 1 | 1, y);
} else if (x > midx) {
que_ri.push_back(q);
} else {
que_up.push_back(q);
}
}
}
solve(midx + 1, sty, que_ri);
solve(stx, midy + 1, que_up);
}
int32_t main() {
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int N, Q;
cin >> L >> N >> Q;
vector<array<int, 3>> que;
for (int i = 1; i <= N; ++i) {
pos0[i].read();
array<int, 3> temp;
temp[0] = 4, temp[1] = i;
que.push_back(temp);
}
int cnt = 0;
while (Q--) {
array<int, 3> q;
cin >> q[0];
if (q[0] != 4) {
cin >> q[1];
} else {
pos0[++N].read();
q[1] = N;
}
if (q[0] == 1) {
q[2] = cnt++;
}
que.push_back(q);
}
solve(0, 0, que);
for (int i = 0; i < cnt; ++i)
cout << ans[i].x << ' ' << ans[i].y << '\n';
return 0;
}
Compilation message
sweeping.cpp:1: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
1 | #pragma gcc optimize("Ofast")
|
sweeping.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
2 | #pragma gcc optimize("O3")
|
sweeping.cpp:3: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
3 | #pragma gcc optimize("fast-math")
|
sweeping.cpp:4: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
4 | #pragma gcc target("avx,avx2,fma,sse,sse2,sse3,sse4,sse4.1,popcnt")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
91420 KB |
Output is correct |
| 2 |
Correct |
58 ms |
90864 KB |
Output is correct |
| 3 |
Correct |
56 ms |
91332 KB |
Output is correct |
| 4 |
Correct |
61 ms |
91336 KB |
Output is correct |
| 5 |
Correct |
58 ms |
91244 KB |
Output is correct |
| 6 |
Incorrect |
53 ms |
90828 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3652 ms |
245292 KB |
Output is correct |
| 2 |
Correct |
3561 ms |
261284 KB |
Output is correct |
| 3 |
Correct |
3517 ms |
261744 KB |
Output is correct |
| 4 |
Correct |
3994 ms |
306292 KB |
Output is correct |
| 5 |
Correct |
9189 ms |
271660 KB |
Output is correct |
| 6 |
Correct |
7210 ms |
288208 KB |
Output is correct |
| 7 |
Correct |
3548 ms |
262268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4054 ms |
251180 KB |
Output is correct |
| 2 |
Correct |
4360 ms |
252956 KB |
Output is correct |
| 3 |
Correct |
2854 ms |
282944 KB |
Output is correct |
| 4 |
Correct |
4754 ms |
370500 KB |
Output is correct |
| 5 |
Correct |
5522 ms |
320692 KB |
Output is correct |
| 6 |
Correct |
3679 ms |
254700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4054 ms |
251180 KB |
Output is correct |
| 2 |
Correct |
4360 ms |
252956 KB |
Output is correct |
| 3 |
Correct |
2854 ms |
282944 KB |
Output is correct |
| 4 |
Correct |
4754 ms |
370500 KB |
Output is correct |
| 5 |
Correct |
5522 ms |
320692 KB |
Output is correct |
| 6 |
Correct |
3679 ms |
254700 KB |
Output is correct |
| 7 |
Correct |
3686 ms |
245708 KB |
Output is correct |
| 8 |
Correct |
3588 ms |
264256 KB |
Output is correct |
| 9 |
Correct |
3553 ms |
253748 KB |
Output is correct |
| 10 |
Correct |
4268 ms |
292324 KB |
Output is correct |
| 11 |
Correct |
6738 ms |
345548 KB |
Output is correct |
| 12 |
Correct |
9542 ms |
306672 KB |
Output is correct |
| 13 |
Correct |
7897 ms |
405624 KB |
Output is correct |
| 14 |
Incorrect |
215 ms |
117860 KB |
Output isn't correct |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
91420 KB |
Output is correct |
| 2 |
Correct |
58 ms |
90864 KB |
Output is correct |
| 3 |
Correct |
56 ms |
91332 KB |
Output is correct |
| 4 |
Correct |
61 ms |
91336 KB |
Output is correct |
| 5 |
Correct |
58 ms |
91244 KB |
Output is correct |
| 6 |
Incorrect |
53 ms |
90828 KB |
Output isn't correct |
