#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 maxN = 1.5e6 + 6;
const int maxQ = 1e6 + 6;
const int K = 1111;
int L, N, Q;
int P[maxN][2];
int spawnT[maxN];
struct Query {
int d, l;
} buf[K + 3];
int sz;
int rx[2][K], X[2];
int bgY[K];
int f[K][K][2];
void rec() {
// cerr << "rec" << endl;
// for (int i = 1; i <= N; ++i) if (spawnT[i] == 0) debug(i, P[i][0], P[i][1]);
// for (int t = 0; t < sz; ++t) {
// auto& q = buf[t];
// cerr << (q.d == 0 ? 'V' : 'H') << ' ' << q.l << endl;
// }
X[0] = X[1] = 0;
for (int t = 0; t < sz; ++t) {
auto& q = buf[t];
rx[q.d][X[q.d]++] = q.l;
rx[q.d ^ 1][X[q.d ^ 1]++] = L - q.l;
}
for (int a = 0; a < 2; ++a) {
sort(rx[a], rx[a] + X[a]);
X[a] = unique(rx[a], rx[a] + X[a]) - rx[a];
// debug(a);
// mdebug(rx[a], X[a]);
}
// for (int t = 0; t < sz; ++t) {
// auto& q = buf[t];
// newCoord[t] = lower_bound(rx[q.d ^ 1], rx[q.d ^ 1] + X[q.d ^ 1], L - q.l) - rx[q.d ^ 1];
// }
fill(bgY, bgY + X[0], 0);
memset(f, 0, sizeof f);
for (int t = 0; t < sz; ++t) {
int ql = buf[t].l;
int qd = buf[t].d;
if (qd == 0) { // V
for (int i = 0; i < X[0] && rx[0][i] <= ql; ++i) {
for (; bgY[i] < X[1] && rx[1][bgY[i]] < L - ql; ++bgY[i]) {
f[i][bgY[i]][1] = 1;
}
if (bgY[i] < X[1] && rx[1][bgY[i]] == L - ql)
f[i][bgY[i]][1] = 2;
}
} else { // H
for (int i = 0; i < X[0] && rx[0][i] <= L - ql; ++i) {
if (rx[0][i] == L - ql) {
for (int j = bgY[i]; j < X[1] && rx[1][j] <= ql; ++j) {
f[i][j][0] = 2;
}
break;
}
for (; bgY[i] < X[1] && rx[1][bgY[i]] <= ql; ++bgY[i]) {
f[i][bgY[i]][0] = 1;
}
}
}
}
for (int i = X[0] - 1; i >= 0; --i)
for (int j = X[1] - 1; j >= 0; --j) {
// debug(i, j, f[i][j][0], f[i][j][1]);
if (f[i][j][1] == 1) {
f[i][j][0] = f[i][j + 1][0];
f[i][j][1] = f[i][j + 1][1];
if (f[i][j][1] == -1)
f[i][j][1] = rx[1][j + 1];
} else if (f[i][j][0] == 1) {
f[i][j][0] = f[i + 1][j][0];
f[i][j][1] = f[i + 1][j][1];
if (f[i][j][0] == -1)
f[i][j][0] = rx[0][i + 1];
} else {
f[i][j][0] = (f[i][j][0] == 0 ? -1 : rx[0][i]);
f[i][j][1] = (f[i][j][1] == 0 ? -1 : rx[1][j]);
}
// debug(i, j, f[i][j][0], f[i][j][1]);
}
for (int i = 1; i <= N; ++i) {
if (spawnT[i] != 0) {
for (int t = spawnT[i]; t < sz; ++t) {
auto& q = buf[t];
if (P[i][q.d] <= q.l)
chkmax(P[i][q.d ^ 1], L - q.l);
}
spawnT[i] = 0;
continue;
}
int c0 = lower_bound(rx[0], rx[0] + X[0], P[i][0]) - rx[0];
int c1 = lower_bound(rx[1], rx[1] + X[1], P[i][1]) - rx[1];
// debug(i, c[0], c[1]);
if (c0 < X[0] && c1 < X[1] && rx[0][c0] + rx[1][c1] <= L) {
if (f[c0][c1][0] != -1)
P[i][0] = f[c0][c1][0];
if (f[c0][c1][1] != -1)
P[i][1] = f[c0][c1][1];
}
// debug(i, P[i][0], P[i][1]);
spawnT[i] = 0;
}
// for (int i = 1; i <= N; ++i)
// debug(i, P[i][0], P[i][1]);
sz = 0;
}
int32_t main() {
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
/*L = 1e9;
N = 5e5;
Q = 1e6;
auto f = [&](ll K) -> ll {
return Q * K + (Q / K + 1) * (K * K * 2 + (N + Q) * (log2(K) + 1));
};
ll mn = 1e18;
int minK = -1;
for (int K = 1; K <= Q; ++K) {
if (chkmin(mn, f(K)))
minK = K;
}
debug(minK, mn / 1e8);
exit(0);/**/
cin >> L >> N >> Q;
for (int i = 1; i <= N; ++i) {
cin >> P[i][0] >> P[i][1];
}
sz = 0;
while (Q--) {
int tp;
cin >> tp;
if (tp == 1) {
int i;
cin >> i;
int p[2] = {P[i][0], P[i][1]};
for (int t = spawnT[i]; t < sz; ++t) {
int qd = buf[t].d;
int ql = buf[t].l;
if (p[qd] <= ql)
chkmax(p[qd ^ 1], L - ql);
}
#ifdef LOCAL
if (N > 20) continue;
#endif
cout << p[0] << ' ' << p[1] << '\n';
} else if (tp == 2) {
int l;
cin >> l;
buf[sz++] = {1, l};
} else if (tp == 3) {
int l;
cin >> l;
buf[sz++] = {0, l};
} else {
++N;
spawnT[N] = sz;
cin >> P[N][0] >> P[N][1];
}
if (sz >= K) {
rec();
}
}
debug(Time);
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")
|
sweeping.cpp:196:13: warning: "/*" within comment [-Wcomment]
196 | exit(0);/**/
|
sweeping.cpp: In function 'int32_t main()':
sweeping.cpp:44:24: warning: statement has no effect [-Wunused-value]
44 | #define debug(...) 1337
| ^~~~
sweeping.cpp:237:5: note: in expansion of macro 'debug'
237 | debug(Time);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
10060 KB |
Output is correct |
| 2 |
Correct |
21 ms |
10060 KB |
Output is correct |
| 3 |
Correct |
4 ms |
460 KB |
Output is correct |
| 4 |
Correct |
21 ms |
10060 KB |
Output is correct |
| 5 |
Correct |
17 ms |
10088 KB |
Output is correct |
| 6 |
Correct |
12 ms |
10056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18090 ms |
22220 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11747 ms |
25824 KB |
Output is correct |
| 2 |
Correct |
12171 ms |
25792 KB |
Output is correct |
| 3 |
Correct |
10990 ms |
25292 KB |
Output is correct |
| 4 |
Correct |
11128 ms |
25732 KB |
Output is correct |
| 5 |
Correct |
11747 ms |
25760 KB |
Output is correct |
| 6 |
Correct |
12046 ms |
25696 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11747 ms |
25824 KB |
Output is correct |
| 2 |
Correct |
12171 ms |
25792 KB |
Output is correct |
| 3 |
Correct |
10990 ms |
25292 KB |
Output is correct |
| 4 |
Correct |
11128 ms |
25732 KB |
Output is correct |
| 5 |
Correct |
11747 ms |
25760 KB |
Output is correct |
| 6 |
Correct |
12046 ms |
25696 KB |
Output is correct |
| 7 |
Execution timed out |
18086 ms |
20988 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
10060 KB |
Output is correct |
| 2 |
Correct |
21 ms |
10060 KB |
Output is correct |
| 3 |
Correct |
4 ms |
460 KB |
Output is correct |
| 4 |
Correct |
21 ms |
10060 KB |
Output is correct |
| 5 |
Correct |
17 ms |
10088 KB |
Output is correct |
| 6 |
Correct |
12 ms |
10056 KB |
Output is correct |
| 7 |
Execution timed out |
18090 ms |
22220 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
