| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1046997 |
2024-08-07T07:27:20 Z |
우민규(#11023) |
Sweeping (JOI20_sweeping) |
C++17 |
|
311 ms |
115516 KB |
#include <bits/stdc++.h>
using namespace std;
// range max segment tree
struct Seg {
int n;
vector<int> seg;
Seg(int n, int init) : n(n), seg(4 * n, init) {};
void add(int node, int l, int r, int idx, int value) {
if (idx < l || idx >= r) return;
if (l + 1 == r) {
seg[node] = max(seg[node], value);
return;
}
int m = (l + r) / 2;
add(2 * node + 1, l, m, idx, value);
add(2 * node + 2, m, r, idx, value);
seg[node] = max(seg[2 * node + 1], seg[2 * node + 2]);
}
void add(int idx, int value) { add(0, 0, n, idx, value); }
// first j >= i s.t. arr[j] >= value
int find_first_ge(int node, int l, int r, int idx, int value) {
if (r <= idx || seg[node] < value) return r;
if (l + 1 == r) return seg[node] >= value ? l : r;
int m = (l + r) / 2;
int left = find_first_ge(2 * node + 1, l, m, idx, value);
if (left == m) return find_first_ge(2 * node + 2, m, r, idx, value);
return left;
}
int find_first_ge(int idx, int value) {
return find_first_ge(0, 0, n, idx, value);
}
};
struct Rectangle;
vector<pair<int, int>> pts;
vector<Rectangle*> in_what_rect;
struct Rectangle {
int size;
set<pair<int, int>> id_by_x, id_by_y;
Rectangle *up, *right;
int x_lower, y_lower, x_origin, y_origin;
void insert(int id) {
make();
if (pts[id].first >= size) {
pts[id].first -= size;
right->insert(id);
} else if (pts[id].second >= size) {
pts[id].second -= size;
up->insert(id);
} else {
if (pts[id].first < x_lower) {
while (!id_by_x.empty() && id_by_x.begin()->first < x_lower) {
int id = id_by_x.begin()->second;
id_by_x.erase(id_by_x.begin());
pts[id].first = x_lower;
id_by_x.insert({pts[id].first, id});
}
x_lower = 0;
}
id_by_x.insert({pts[id].first, id});
if (pts[id].second < y_lower) {
while (!id_by_y.empty() && id_by_y.begin()->first < y_lower) {
int id = id_by_y.begin()->second;
id_by_y.erase(id_by_y.begin());
pts[id].second = y_lower;
id_by_y.insert({pts[id].second, id});
}
y_lower = 0;
}
id_by_y.insert({pts[id].second, id});
in_what_rect[id] = this;
}
}
// push in x direction
void push_x(int h) {
if (size == 1) return;
make();
if (h <= size - 1) {
while (!id_by_y.empty() &&
max(y_lower, id_by_y.begin()->first) < h) {
int id = id_by_y.begin()->second;
id_by_y.erase(id_by_y.begin());
id_by_x.erase({pts[id].first, id});
pts[id].first = (2 * size - 1 - h) - size;
pts[id].second = max(pts[id].second, y_lower);
right->insert(id);
}
right->push_x(h);
} else if (h == size) {
x_lower = size - 1;
} else {
up->push_x(h - size);
x_lower = max(x_lower, 2 * size - 1 - h);
}
}
void push_y(int h) {
if (size == 1) return;
make();
if (h <= size - 1) {
while (!id_by_x.empty() &&
max(x_lower, id_by_x.begin()->first) < h) {
int id = id_by_x.begin()->second;
id_by_x.erase(id_by_x.begin());
id_by_y.erase({pts[id].second, id});
pts[id].second = (2 * size - 1 - h) - size;
pts[id].first = max(pts[id].first, x_lower);
up->insert(id);
}
up->push_y(h);
} else if (h == size) {
y_lower = size - 1;
} else {
right->push_y(h - size);
y_lower = max(y_lower, 2 * size - 1 - h);
}
}
void make() {
if (up || right) return;
up = new Rectangle;
up->size = size / 2;
up->x_origin = x_origin;
up->y_origin = y_origin + size;
right = new Rectangle;
right->size = size / 2;
right->x_origin = x_origin + size;
right->y_origin = y_origin;
}
};
int n, m, q, n_aligned, y_offset;
vector<int> pts_time;
vector<pair<int, int>> queries;
Rectangle root;
vector<int> xs, ys;
void solve() {
cin >> n >> m >> q;
n_aligned = (1 << (__lg(n + 1) + 1)) - 2;
y_offset = n_aligned - n;
root.x_origin = root.y_origin = root.x_lower = root.y_lower = 0;
root.size = n_aligned / 2 + 1;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
y += y_offset;
pts.push_back({x, y});
in_what_rect.push_back(&root);
root.insert(pts.size() - 1);
}
for (int i = 0; i < q; ++i) {
int t;
cin >> t;
if (t == 1) {
int p;
cin >> p;
p -= 1;
Rectangle *rect = in_what_rect[p];
if (rect == nullptr) {
cout << "fail\n";
return;
}
pair<int, int> pts_offset = pts[p];
pts_offset.first = max(pts_offset.first, rect->x_lower);
pts_offset.second = max(pts_offset.second, rect->y_lower);
pair<int, int> pts_origin = {rect->x_origin, rect->y_origin};
pair<int, int> pts_with_y = {pts_offset.first + pts_origin.first,
pts_offset.second + pts_origin.second};
cout << pts_with_y.first << " " << pts_with_y.second - y_offset << "\n";
}
if (t == 2) {
int h;
cin >> h;
root.push_x(h + y_offset + 1);
}
if (t == 3) {
int h;
cin >> h;
root.push_y(h + 1);
}
if (t == 4) {
int x, y;
cin >> x >> y;
y += y_offset;
pts.push_back({x, y});
in_what_rect.push_back(&root);
root.insert(pts.size() - 1);
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
solve();
}
Compilation message
sweeping.cpp: In function 'int main()':
sweeping.cpp:213:9: warning: unused variable 't' [-Wunused-variable]
213 | int t = 1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
311 ms |
115516 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
311 ms |
115516 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
