#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 = 185;
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 f[K + 1][K][K][2];
void rec() {
// cerr << "rec" << endl;
// 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];
}
}
}
}
for (int i = 1; i <= N; ++i) {
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) {
int t = spawnT[i];
for (int a = 0; a < 2; ++a) {
if (f[t][c[0]][c[1]][a] != -1) {
P[i][a] = f[t][c[0]][c[1]][a];
}
}
}
// debug(i, P[i][0], P[i][1]);
spawnT[i] = 0;
}
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 * 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:167:13: warning: "/*" within comment [-Wcomment]
167 | 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:207:5: note: in expansion of macro 'debug'
207 | debug(Time);
| ^~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
89 ms |
50248 KB |
Output is correct |
| 2 |
Correct |
140 ms |
50340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
460 KB |
Output is correct |
| 4 |
Correct |
92 ms |
50324 KB |
Output is correct |
| 5 |
Correct |
171 ms |
47116 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1484 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
18103 ms |
58876 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
18031 ms |
60708 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
18031 ms |
60708 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
89 ms |
50248 KB |
Output is correct |
| 2 |
Correct |
140 ms |
50340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
460 KB |
Output is correct |
| 4 |
Correct |
92 ms |
50324 KB |
Output is correct |
| 5 |
Correct |
171 ms |
47116 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1484 KB |
Output is correct |
| 7 |
Execution timed out |
18103 ms |
58876 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
