#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 = 900;
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 newCoord[K];
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];
// }
// for (int i = 0; i < X[0]; ++i)
// for (int j = 0; j < X[1] && rx[0][i] + rx[1][j] <= L; ++j)
// f[sz][i][j][0] = f[sz][i][j][1] = -1;
// int p[2];
// for (int t = sz - 1; t >= 0; --t) {
// auto& q = buf[t];
// int nc = newCoord[t];
// for (int i = 0; i < X[0]; ++i) {
// p[0] = rx[0][i];
// for (int j = 0; j < X[1] && p[0] + rx[1][j] <= L; ++j) {
// p[1] = rx[1][j];
// if (p[q.d] <= q.l && p[q.d ^ 1] <= L - q.l) {
// if (!q.d) {
// f[t][i][j][0] = f[t + 1][i][nc][0];
// f[t][i][j][1] = f[t + 1][i][nc][1];
// if (f[t][i][j][1] == -1) {
// f[t][i][j][1] = L - q.l;
// }
// } else {
// f[t][i][j][0] = f[t + 1][nc][j][0];
// f[t][i][j][1] = f[t + 1][nc][j][1];
// if (f[t][i][j][0] == -1) {
// f[t][i][j][0] = L - q.l;
// }
// }
// } else {
// f[t][i][j][0] = f[t + 1][i][j][0];
// f[t][i][j][1] = f[t + 1][i][j][1];
// }
// }
// }
// }
fill(bgY, bgY + X[0], 0);
memset(f, 0, sizeof f);
for (int t = 0; t < sz; ++t) {
auto& q = buf[t];
if (q.d == 0) { // V
for (int i = 0; i < X[0] && rx[0][i] <= q.l; ++i) {
for (; bgY[i] < X[1] && rx[1][bgY[i]] < L - q.l; ++bgY[i]) {
f[i][bgY[i]][1] = 1;
}
if (bgY[i] < X[1] && rx[1][bgY[i]] == L - q.l)
f[i][bgY[i]][1] = 2;
}
} else { // H
for (int i = 0; i < X[0] && rx[0][i] <= L - q.l; ++i) {
if (rx[0][i] == L - q.l) {
for (int j = bgY[i]; j < X[1] && rx[1][j] <= q.l; ++j) {
f[i][j][0] = 2;
}
break;
}
for (; bgY[i] < X[1] && rx[1][bgY[i]] <= q.l; ++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 c[2];
for (int a = 0; a < 2; ++a) {
c[a] = lower_bound(rx[a], rx[a] + X[a], P[i][a]) - rx[a];
}
// debug(i, c[0], c[1]);
if (c[0] < X[0] && c[1] < X[1] && rx[0][c[0]] + rx[1][c[1]] <= L) {
for (int a = 0; a < 2; ++a) {
if (f[c[0]][c[1]][a] != -1) {
P[i][a] = f[c[0]][c[1]][a];
}
}
}
// 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) {
auto& q = buf[t];
if (p[q.d] <= q.l)
chkmax(p[q.d ^ 1], L - q.l);
}
#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:227:13: warning: "/*" within comment [-Wcomment]
227 | exit(0);/**/
|
sweeping.cpp: In function 'int32_t main()':
sweeping.cpp:40:24: warning: statement has no effect [-Wunused-value]
40 | #define debug(...) 1337
| ^~~~
sweeping.cpp:267:5: note: in expansion of macro 'debug'
267 | debug(Time);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
6856 KB |
Output is correct |
| 2 |
Correct |
18 ms |
6732 KB |
Output is correct |
| 3 |
Correct |
3 ms |
460 KB |
Output is correct |
| 4 |
Correct |
15 ms |
6860 KB |
Output is correct |
| 5 |
Correct |
16 ms |
6776 KB |
Output is correct |
| 6 |
Correct |
9 ms |
6744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18089 ms |
19432 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11584 ms |
23236 KB |
Output is correct |
| 2 |
Correct |
11563 ms |
22472 KB |
Output is correct |
| 3 |
Correct |
11526 ms |
22124 KB |
Output is correct |
| 4 |
Correct |
11599 ms |
22504 KB |
Output is correct |
| 5 |
Correct |
11431 ms |
22356 KB |
Output is correct |
| 6 |
Correct |
11526 ms |
22428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11584 ms |
23236 KB |
Output is correct |
| 2 |
Correct |
11563 ms |
22472 KB |
Output is correct |
| 3 |
Correct |
11526 ms |
22124 KB |
Output is correct |
| 4 |
Correct |
11599 ms |
22504 KB |
Output is correct |
| 5 |
Correct |
11431 ms |
22356 KB |
Output is correct |
| 6 |
Correct |
11526 ms |
22428 KB |
Output is correct |
| 7 |
Execution timed out |
18060 ms |
17496 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
6856 KB |
Output is correct |
| 2 |
Correct |
18 ms |
6732 KB |
Output is correct |
| 3 |
Correct |
3 ms |
460 KB |
Output is correct |
| 4 |
Correct |
15 ms |
6860 KB |
Output is correct |
| 5 |
Correct |
16 ms |
6776 KB |
Output is correct |
| 6 |
Correct |
9 ms |
6744 KB |
Output is correct |
| 7 |
Execution timed out |
18089 ms |
19432 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
