| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1047004 |
2024-08-07T07:33:05 Z |
우민규(#11023) |
Sweeping (JOI20_sweeping) |
C++17 |
|
18000 ms |
1578412 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->up = up->right = nullptr;
up->size = size / 2;
up->x_origin = x_origin;
up->y_origin = y_origin + size;
right = new Rectangle;
right->up = right->right = nullptr;
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];
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:211:9: warning: unused variable 't' [-Wunused-variable]
211 | int t = 1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7004 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
860 KB |
Output is correct |
| 4 |
Correct |
6 ms |
6812 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1112 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2289 ms |
1525076 KB |
Output is correct |
| 2 |
Correct |
2236 ms |
1545068 KB |
Output is correct |
| 3 |
Correct |
2223 ms |
1545624 KB |
Output is correct |
| 4 |
Correct |
1799 ms |
1164804 KB |
Output is correct |
| 5 |
Execution timed out |
18060 ms |
444436 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2095 ms |
1501484 KB |
Output is correct |
| 2 |
Correct |
2028 ms |
1337988 KB |
Output is correct |
| 3 |
Correct |
1161 ms |
1391676 KB |
Output is correct |
| 4 |
Correct |
2066 ms |
1392184 KB |
Output is correct |
| 5 |
Correct |
2256 ms |
1391736 KB |
Output is correct |
| 6 |
Correct |
1953 ms |
1425380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2095 ms |
1501484 KB |
Output is correct |
| 2 |
Correct |
2028 ms |
1337988 KB |
Output is correct |
| 3 |
Correct |
1161 ms |
1391676 KB |
Output is correct |
| 4 |
Correct |
2066 ms |
1392184 KB |
Output is correct |
| 5 |
Correct |
2256 ms |
1391736 KB |
Output is correct |
| 6 |
Correct |
1953 ms |
1425380 KB |
Output is correct |
| 7 |
Correct |
2482 ms |
1477368 KB |
Output is correct |
| 8 |
Correct |
2460 ms |
1466764 KB |
Output is correct |
| 9 |
Correct |
2127 ms |
1467620 KB |
Output is correct |
| 10 |
Correct |
1856 ms |
1380628 KB |
Output is correct |
| 11 |
Correct |
2679 ms |
1381656 KB |
Output is correct |
| 12 |
Correct |
3108 ms |
1415664 KB |
Output is correct |
| 13 |
Correct |
3179 ms |
1382684 KB |
Output is correct |
| 14 |
Correct |
55 ms |
348 KB |
Output is correct |
| 15 |
Correct |
716 ms |
69984 KB |
Output is correct |
| 16 |
Correct |
2187 ms |
1577336 KB |
Output is correct |
| 17 |
Correct |
2228 ms |
1578412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7004 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10332 KB |
Output is correct |
| 3 |
Correct |
2 ms |
860 KB |
Output is correct |
| 4 |
Correct |
6 ms |
6812 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1112 KB |
Output is correct |
| 6 |
Correct |
1 ms |
604 KB |
Output is correct |
| 7 |
Correct |
2289 ms |
1525076 KB |
Output is correct |
| 8 |
Correct |
2236 ms |
1545068 KB |
Output is correct |
| 9 |
Correct |
2223 ms |
1545624 KB |
Output is correct |
| 10 |
Correct |
1799 ms |
1164804 KB |
Output is correct |
| 11 |
Execution timed out |
18060 ms |
444436 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
