#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
const int N = 8e4 + 10;
set <int> ms[N << 1];
bool IsRoot[N << 1];
int n, m, par[N], ans[N];
vector <int> g[N << 1];
vector <int> X, Y;
void compress(vector <int> &v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
struct event {
int val, l, r;
event () {}
event (int VAL, int L, int R) {
val = VAL;
l = L;
r = R;
}
};
vector <event> ev[N * 3];
vector <int> point[N * 3];
struct rec {
int x1, y1, x2, y2, id;
void inp() {
cin >> x1 >> y1 >> x2 >> y2;
X.push_back(x1); X.push_back(x2);
Y.push_back(y1); Y.push_back(y2);
}
bool operator < (const rec &o) const {
if (x1 == o.x1) return y1 < o.y1;
return x1 < o.x1;
}
} a[N];
struct shoot {
int x, y, k;
void inp() {
cin >> x >> y >> k;
X.push_back(x);
Y.push_back(y);
}
} p[N];
struct SEG {
int val[N * 12], lazy[N * 12];
SEG () {
fill_n(val, N * 12, 0);
fill_n(lazy, N * 12, -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 L, int R, int VAL, int id) {
if (l > R || r < L) return;
if (l >= L && r <= R) {
change(id, VAL);
return;
}
int mid = (l + r) >> 1;
down(id);
update(l, mid, L, R, VAL, id << 1);
update(mid + 1, r, L, R, VAL, id << 1 | 1);
val[id] = max(val[id << 1], val[id << 1 | 1]);
}
int get(int l, int r, int u, int id) {
if (l == r) return val[id];
int mid = (l + r) >> 1;
down(id);
if (u <= mid) return get(l, mid, u, id << 1);
return get(mid + 1, r, u, id << 1 | 1);
}
} seg;
int ID(int p, vector <int> &v) {
return lower_bound(v.begin(), v.end(), p) - v.begin() + 1;
}
void DFS(int s) {
if (s > n) {
ms[s].insert(p[s - n].k);
}
for (int z: g[s]) {
DFS(z);
if (ms[z].size() > ms[s].size()) swap(ms[z], ms[s]);
for (int kk: ms[z]) {
ms[s].insert(kk);
}
}
if (s <= n) {
ans[a[s].id] = ms[s].size();
}
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
a[i].inp();
a[i].id = i;
}
for (int i = 1; i <= m; ++i) p[i].inp();
sort(a + 1, a + n + 1);
compress(X);
compress(Y);
for (int i = 1; i <= n; ++i) {
a[i].x1 = ID(a[i].x1, X);
a[i].x2 = ID(a[i].x2, X);
a[i].y1 = ID(a[i].y1, Y);
a[i].y2 = ID(a[i].y2, Y);
ev[a[i].x1].push_back(event(i, a[i].y1, a[i].y2));
ev[a[i].x2].push_back(event(-i, a[i].y1, a[i].y2));
IsRoot[i] = true;
}
for (int i = 1; i <= m; ++i) {
p[i].x = ID(p[i].x, X);
p[i].y = ID(p[i].y, Y);
point[p[i].x].push_back(i);
IsRoot[i + n] = true;
}
for (int i = 1; i <= (int)X.size(); ++i) {
for (event z: ev[i]) {
if (z.val > 0) {
int kk = seg.get(1, Y.size(), z.l, 1);
if (kk) {
par[z.val] = kk;
g[kk].push_back(z.val);
IsRoot[z.val] = false;
}
seg.update(1, Y.size(), z.l, z.r, z.val, 1);
}
}
for (int z: point[i]) {
int kk = seg.get(1, Y.size(), p[z].y, 1);
if (kk) {
g[kk].push_back(z + n);
IsRoot[z + n] = false;
}
}
for (event z: ev[i]) {
if (z.val < 0) {
seg.update(1, Y.size(), z.l, z.r, par[-z.val], 1);
}
}
}
for (int i = 1; i <= n + m; ++i) {
if (IsRoot[i]) DFS(i);
}
for (int i = 1; i <= n; ++i) cout << ans[i] << "\n";
return 0;
}
# | 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... |