#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define all(x) begin(x), end(x)
#define x first
#define y second
typedef long long ll;
typedef long double ld;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<T>>;
const int MAX_N = 1 << 18, MAX_TREE = 1 << 19, MAX_M = 8e4 + 10, INF = 0x3f3f3f3f;
struct Event {
char type; // 0 - open, 1 - shoot, 2 - close
int x, y0, y1, id;
};
vector<Event> events;
bool operator<(const Event &a, const Event &b) {
if (a.x < b.x)
return 1;
if (a.x > b.x)
return 0;
if (a.type < b.type)
return 1;
if (a.type > b.type)
return 0;
return 0;
}
vector<pair<int, int>> tree1[MAX_TREE];
void addRect(const Event &e) {
int y0 = e.y0 + MAX_N;
int y1 = e.y1 + MAX_N;
while (y0 <= y1) {
if (y0 & 1) tree1[y0].push_back({e.x, e.id});
if (!(y1 & 1)) tree1[y1].push_back({e.x, e.id});
y0 = (y0 + 1) / 2;
y1 = (y1 - 1) / 2;
}
}
void removeRect(const Event &e) {
int y0 = e.y0 + MAX_N;
int y1 = e.y1 + MAX_N;
while (y0 <= y1) {
if ((y0 & 1) && tree1[y0].size()) {
assert(tree1[y0].back().y == e.id);
tree1[y0].pop_back();
}
if (!(y1 & 1) && tree1[y1].size()) {
assert(tree1[y1].back().y == e.id);
tree1[y1].pop_back();
}
y0 = (y0 + 1) / 2;
y1 = (y1 - 1) / 2;
}
}
int getOwner(const Event &e) {
int i = e.y0 + MAX_N;
pair<int, int> res{-INF, 0};
while (i) {
if (tree1[i].size() && tree1[i].back() > res)
res = tree1[i].back();
i /= 2;
}
return res.y;
}
vector<int> childrens[MAX_M];
set<int> owned[MAX_M];
int ans[MAX_N];
set<int> *dfs(int u) {
vector<pair<int, set<int>*>> cs;
for (int v : childrens[u]) {
auto res = dfs(v);
cs.push_back({res->size(), res});
}
if (cs.size() == 0) {
ans[u] = (int) owned[u].size();
return &owned[u];
}
set<int> *v = max_element(all(cs))->y;
for (auto p : cs) {
if (p.y != v)
v->insert(p.y->begin(), p.y->end());
}
v->insert(all(owned[u]));
ans[u] = (int) v->size();
return v;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
map<int, int> yremap;
for (int i = 0; i < n; ++i) {
int x0, y0, x1, y1;
cin >> x0 >> y0 >> x1 >> y1;
events.push_back({0, x0, y0, y1, i + 1});
events.push_back({2, x1, y0, y1, i + 1});
yremap[y0] = yremap[y1] = 0;
}
for (int i = 0; i < m; ++i) {
int x, y, k;
cin >> x >> y >> k;
events.push_back({1, x, y, y, k});
yremap[y] = 0;
}
int cnt = 0;
for (auto &p : yremap)
p.y = cnt++;
assert(cnt < MAX_N);
for (auto &e : events)
e.y0 = yremap[e.y0], e.y1 = yremap[e.y1];
sort(all(events));
for (auto e : events) {
if (e.type == 0) {
childrens[getOwner(e)].push_back(e.id);
addRect(e);
} else if (e.type == 1) {
owned[getOwner(e)].insert(e.id);
} else if (e.type == 2) {
removeRect(e);
}
}
dfs(0);
for (int i = 1; i <= n; ++i)
cout << ans[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
29444 KB |
Output is correct |
| 2 |
Correct |
135 ms |
29572 KB |
Output is correct |
| 3 |
Correct |
16 ms |
18304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
33644 KB |
Output is correct |
| 2 |
Correct |
173 ms |
31876 KB |
Output is correct |
| 3 |
Correct |
15 ms |
18304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
306 ms |
45816 KB |
Output is correct |
| 2 |
Correct |
294 ms |
39400 KB |
Output is correct |
| 3 |
Correct |
15 ms |
18304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
548 ms |
62456 KB |
Output is correct |
| 2 |
Correct |
546 ms |
52944 KB |
Output is correct |
| 3 |
Correct |
15 ms |
18304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
554 ms |
59476 KB |
Output is correct |
| 2 |
Correct |
477 ms |
50560 KB |
Output is correct |
| 3 |
Correct |
15 ms |
18304 KB |
Output is correct |
