//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define trav(x,a) for (const auto& x: a)
#define sz(x) (int)(x).size()
#define pii pair<int, int>
#define vii vector<pii>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
const int inf = 1e9 + 7;
const int N = 1e6 + 5;
pii a[N], b[N];
int idx[N], n;
pii ans[N], qry[N];
vector<pii> seg[N];
void upd(int l, int r, int k, int x, int y, int i, int j) {
if (r < x || y < l) return;
if (x <= l && r <= y) {
seg[k].push_back({i, j});
return;
}
int m = (l+r) / 2;
upd(l, m, k*2, x, y, i, j);
upd(m+1, r, k*2+1, x, y, i, j);
}
void solve(int l, int r, int k) {
if (l < r) {
int m = (l+r) / 2;
solve(l, m, k*2);
solve(m+1, r, k*2+1);
}
if (seg[k].empty())
return;
sort(seg[k].begin(), seg[k].end(), [](pii lhs, pii rhs) {
return b[lhs.nd] < b[rhs.nd];
});
map<pii,pii> q;
q[{n, n}] = {0, 0};
for (int i = l; i <= r; i++) {
int L = qry[i].nd;
if (qry[i].st == 2) { // H
auto it = q.lower_bound({n - L, L});
if (it->st.nd == L)
continue;
pii x = it->st, y = it->nd;
q.erase(it);
q[{x.st, L}] = y;
q[{n - L - 1, x.nd}] = {y.st, L + 1};
} else { // V
auto it = q.lower_bound({L, n - L});
if (it->st.st == L)
continue;
pii x = it->st, y = it->nd;
q.erase(it);
q[{L, x.nd}] = y;
q[{x.st, n - L - 1}] = {L + 1, y.nd};
}
}
vector<pair<pii,pii>> arr;
trav(x, q) arr.push_back(x);
sort(arr.begin(), arr.end(), [](pair<pii,pii> lhs, pair<pii,pii> rhs) {
return lhs.nd < rhs.nd;
});
int i = 0;
map<int,pii> act;
trav(x, seg[k]) {
while (i < sz(arr) && arr[i].nd.st <= b[x.nd].st) {
act[arr[i].nd.nd] = arr[i].st;
i++;
}
auto it = prev(act.upper_bound(b[x.nd].nd));
b[x.nd].st = max(b[x.nd].st, n - it->nd.nd);
b[x.nd].nd = max(b[x.nd].nd, n - it->nd.st);
ans[x.st] = b[x.nd];
}
}
int main() {
int m, q; scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &a[i].st, &a[i].nd);
b[i] = a[i];
idx[i] = 1;
}
vector<array<int,4>> ar;
int j = 0;
for (int i = 1; i <= q; i++) {
ans[i] = mp(-1, -1);
int t, x, y;
scanf("%d %d", &t, &x);
if (t == 1) {
ar.push_back({idx[x], j, i, x});
idx[x] = j+1;
} else if (t <= 3) {
qry[++j] = mp(t, x);
} else if (t == 4) {
scanf("%d", &y);
a[++m] = mp(x, y);
b[m] = a[m];
idx[m] = j+1;
}
}
trav(x, ar)
if (x[0] <= x[1] && j)
upd(1, j, 1, x[0], x[1], x[2], x[3]);
solve(1, j, 1);
trav(x, ar) {
if (ans[x[2]] != mp(-1, -1))
a[x[3]] = ans[x[2]];
printf("%d %d\n", a[x[3]].st, a[x[3]].nd);
}
return 0;
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int m, q; scanf("%d %d %d", &n, &m, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a[i].st, &a[i].nd);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &t, &x);
~~~~~^~~~~~~~~~~~~~~~~
sweeping.cpp:102:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &y);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
24448 KB |
Output is correct |
| 2 |
Correct |
38 ms |
24312 KB |
Output is correct |
| 3 |
Correct |
31 ms |
24192 KB |
Output is correct |
| 4 |
Correct |
29 ms |
24448 KB |
Output is correct |
| 5 |
Correct |
20 ms |
24064 KB |
Output is correct |
| 6 |
Correct |
23 ms |
24320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
943 ms |
214840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
871 ms |
205844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
871 ms |
205844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
24448 KB |
Output is correct |
| 2 |
Correct |
38 ms |
24312 KB |
Output is correct |
| 3 |
Correct |
31 ms |
24192 KB |
Output is correct |
| 4 |
Correct |
29 ms |
24448 KB |
Output is correct |
| 5 |
Correct |
20 ms |
24064 KB |
Output is correct |
| 6 |
Correct |
23 ms |
24320 KB |
Output is correct |
| 7 |
Runtime error |
943 ms |
214840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Halted |
0 ms |
0 KB |
- |
