#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
const int N = 1.6e5 + 1;
int n, m, ans[N], par[N];
std::set <int> s[N];
std::vector <int> v[N], Y;
std::vector < std::pair < std::pair <int, int>, int > > events;
bool IsRoot[N];
struct SegmentTree {
int val[N << 2], lazy[N << 2];
SegmentTree() {
std::fill_n(val, N << 2, 0);
std::fill_n(lazy, N << 2, -1);
}
void change (int id, int VAL) {
val[id] = lazy[id] = VAL;
}
void down(int id) {
if (lazy[id] == -1) return;
change(id << 1, lazy[id]);
change(id << 1 | 1, lazy[id]);
lazy[id] = -1;
}
void update(int l, int r, int A, int B, int VAL, int id) {
if (l > B || r < A) return;
if (l >= A && r <= B) {
change(id, VAL);
return;
}
int mid = (l + r) >> 1;
down(id);
update(l, mid, A, B, VAL, id << 1);
update(mid + 1, r, A, B, VAL, id << 1 | 1);
val[id] = std::max(val[id << 1], val[id << 1 | 1]);
}
int get(int l, int r, int A, int B, int id) {
if (l > B || r < A) return -1;
if (l >= A && r <= B) return val[id];
int mid = (l + r) >> 1;
down(id);
return std::max(get(l, mid, A, B, id << 1), get(mid + 1, r, A, B, id << 1 | 1));
}
} seg;
struct rect {
int x1, y1, x2, y2;
int id, k;
void input(int i) {
if (i <= n) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
k = -1;
} else {
scanf("%d%d%d", &x1, &y1, &k);
x2 = x1;
y2 = y1;
}
Y.push_back(y1);
Y.push_back(y2);
id = i;
}
void output() {
printf("%d %d %d %d\n", x1, y1, x2, y2);
}
bool in (int l, int r, int u) {
return u >= l && u <= r;
}
bool rect_in (rect o) {
return in(x1, x2, o.x1) && in(x1, x2, o.x2) && in(y1, y2, o.y1) && in(y1, y2, o.y2);
}
} a[N];
bool cmp (rect x, rect y) {
if (std::pair <int, int>(x.x1, x.y1) == std::pair <int, int>(y.x1, y.y1)) return std::pair <int, int>(x.x2, x.y2) < std::pair <int, int>(y.x2, y.y2);
return std::pair <int, int>(x.x1, x.y1) < std::pair <int, int>(y.x1, y.y1);
}
std::unordered_map <int, int> ID;
int GetID(int p) {
return ID[p];
}
void DFS(int u) {
if (a[u].k != -1) {
s[u].insert(a[u].k);
}
for (int z: v[u]) {
DFS(z);
if (s[u].size() > s[z].size()) s[u].swap(s[z]);
for (int j: s[z]) s[u].insert(j);
s[z].clear();
}
ans[a[u].id] = s[u].size();
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n + m; ++i) {
a[i].input(i);
IsRoot[i] = true;
}
sort(Y.begin(), Y.end());
Y.erase(unique(Y.begin(), Y.end()), Y.end());
for (int i = 0; i < Y.size(); ++i) {
ID[Y[i]] = i + 1;
}
std::sort(a + 1, a + n + m + 1, cmp);
for (int i = 1; i <= n + m; ++i) {
events.push_back(std::pair < std::pair <int, int>, int >(std::pair <int, int>(a[i].x1, a[i].y1), i));
events.push_back(std::pair < std::pair <int, int>, int >(std::pair <int, int>(a[i].x2, a[i].y2), -i));
}
std::sort(events.begin(), events.end());
int j = 0;
for (int i = 1; i <= n + m; ++i) {
while (j < events.size() && events[j].first < std::pair <int, int>(a[i].x1, a[i].y1)) {
int cur = abs(events[j].second);
if (events[j].second > 0) {
seg.update(1, Y.size(), GetID(a[cur].y1), GetID(a[cur].y2), cur, 1);
} else {
int ph = par[cur];
if (ph != 0) seg.update(1, Y.size(), GetID(a[ph].y1), GetID(a[ph].y2), ph, 1);
else seg.update(1, Y.size(), GetID(a[cur].y1), GetID(a[cur].y2), 0, 1);
}
++j;
}
int k = seg.get(1, Y.size(), GetID(a[i].y1), GetID(a[i].y2), 1);
if (k > 0) {
par[i] = k;
v[k].push_back(i);
IsRoot[i] = false;
}
}
for (int i = 1; i <= n + m; ++i) {
if (IsRoot[i]) {
DFS(i);
}
}
for (int i = 1; i <= n; ++i) {
printf("%d\n", ans[i]);
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
plahte.cpp: In function 'int main()':
plahte.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
plahte.cpp: In member function 'void rect::input(int)':
plahte.cpp:68:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:71:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d%d%d", &x1, &y1, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |