#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
const int N = 2e5;
struct Hcn {
int a, b, c, d;
int id, color;
};
bool cmp(Hcn h1, Hcn h2) {
if (h1.c == h2.c) return h1.c - h1.a < h2.c - h2.a;
return h1.c < h2.c;
}
int n, m;
Hcn h[N];
int pa[N];
vector<int> child[N];
struct cmp_Hcn {
bool operator()(int i, int j) const {
return h[i].b < h[j].b;
}
};
void prep() {
sort(h + 1, h + 1 + n + m, cmp);
int cur = 1;
set<int, cmp_Hcn> store;
for (int i = 1; i <= n + m; i ++) {
//cout << h[i].a << " " << h[i].b << " " << h[i].c << " " << h[i].d << "\n";
while (cur <= n + m && h[cur].c <= h[i].a) {
store.erase(cur);
cur ++;
}
if (store.empty()) {
store.insert(i);
continue;
}
auto it = store.lower_bound(i);
vector<int> need_erase;
while (it != store.end()) {
int p = *it;
if (h[p].a >= h[i].a && h[p].c <= h[i].c && h[p].b >= h[i].b && h[p].d <= h[i].d) {
need_erase.push_back(p);
pa[p] = i;
++it;
} else {
break;
}
}
for (int p : need_erase) store.erase(p);
store.insert(i);
}
for (int i = 1; i <= n + m; i ++) {
child[pa[i]].push_back(i);
}
}
int sz[N];
int ans[N];
int cur_ans;
int cur_cnt[N];
void dfs(int u) {
sz[u] = 1;
for (int v : child[u]) {
dfs(v);
sz[u] += sz[v];
}
}
void decre(int u) {
cur_cnt[h[u].color] --;
if (cur_cnt[h[u].color] == 0) cur_ans --;
for (int v : child[u]) {
decre(v);
}
}
void incre(int u) {
cur_cnt[h[u].color] ++;
if (cur_cnt[h[u].color] == 1) cur_ans ++;
for (int v : child[u]) {
incre(v);
}
}
void DFS(int u) {
if (child[u].size() == 0) {
cur_cnt[h[u].color] ++;
if (cur_cnt[h[u].color] == 1) cur_ans ++;
return;
}
int b = 0;
for (int v : child[u]) {
if (b == 0 || sz[v] > sz[b]) b = v;
}
for (int v : child[u]) if (v != b) {
DFS(v);
decre(v);
}
DFS(b);
for (int v : child[u]) if (v != b) {
incre(v);
}
//cout << u << " " << cur_ans << " " << cur_cnt[0] << " " << cur_cnt[1] << " " << cur_cnt[2] << " " << cur_cnt[3] << "\n";
ans[h[u].id] = cur_ans - (cur_cnt[0] > 0);
cur_cnt[h[u].color] ++;
if (cur_cnt[h[u].color] == 1) cur_ans ++;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
cin >> h[i].a >> h[i].b >> h[i].c >> h[i].d;
h[i].id = i;
}
for (int i = 1; i <= m; i ++) {
cin >> h[i + n].a >> h[i + n].b >> h[i + n].color;
h[i + n].c = h[i + n].a;
h[i + n].d = h[i + n].b;
}
prep();
//for (int i = 1; i <= m + n; i ++) cout << i << " " << pa[i] << "\n";
dfs(0);
DFS(0);
for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
}
# | 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... |