#include<bits/stdc++.h>
#define int long long
using namespace std;
#define size(u) (int)(u).size()
#define pb push_back
#define fastio ios::sync_with_stdio(false); cin.tie(nullptr);
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
struct SegmentTree {
int n;
vector<int> t, lazy;
SegmentTree(int n): n(n), t(4*n, -1), lazy(4*n, -2) {}
void apply(int v, int val) {
t[v] = val;
lazy[v] = val;
}
void push(int v) {
if (lazy[v] == -2) return;
apply(2*v, lazy[v]);
apply(2*v+1, lazy[v]);
lazy[v] = -2;
}
void update(int v, int tl, int tr, int l, int r, int val) {
if (l > tr || tl > r) {
return;
} else if (tl >= l && tr <= r) {
apply(v, val);
} else {
push(v);
int mid = (tl + tr) / 2;
update(2*v, tl, mid, l, r, val);
update(2*v+1, mid+1, tr, l, r, val);
}
}
void update(int l, int r, int val) {
update(1, 0, n-1, l, r, val);
}
int query(int v, int tl, int tr, int pos) {
if (tl == tr) {
return t[v];
} else {
push(v);
int mid = (tl + tr) / 2;
if (pos <= mid) return query(2*v, tl, mid, pos);
else return query(2*v+1, mid+1, tr, pos);
}
}
int query(int pos) {
return query(1, 0, n-1, pos);
}
};
constexpr int N = 80004;
struct point {
int x, y, id, prior;
bool query = false;
bool operator<(point o) {
if (x < o.x) return true;
if (x > o.x) return false;
return prior < o.prior;
}
};
ostream& operator<<(ostream& out, point p) {
return out << p.x << ' ' << p.y << ' ' << p.id << ' ' << p.query;
}
struct sq {
int l, r;
} squares[N];
int q[N], parent[N], ans[N];
set<int> smtol[N];
vector<int> ch[N];
vector<int> yvals;
bool open[N];
int getyval(int a) {
return lower_bound(all(yvals), a) - yvals.begin();
}
void dfs(int cur) {
for (auto u : ch[cur]) {
dfs(u);
if (size(smtol[u]) > size(smtol[cur])) smtol[u].swap(smtol[cur]);
for (auto t : smtol[u]) smtol[cur].insert(t);
}
ans[cur] = size(smtol[cur]);
}
signed main() {
fastio;
int n, m; cin >> n >> m;
vector<point> points;
for (int i = 0; i < n; i++) {
point p1, p2;
cin >> p1.x >> p1.y >> p2.x >> p2.y;
p1.id = p2.id = i;
p1.prior = -2, p2.prior = 0;
points.pb(p1); points.pb(p2);
yvals.pb(p1.y); yvals.pb(p2.y);
squares[i] = {p1.y, p2.y};
}
for (int i = 0; i < m; i++) {
point p; cin >> p.x >> p.y;
p.id = i, p.query = true;
p.prior = -1;
points.pb(p);
yvals.pb(p.y);
cin >> q[i];
}
sort(all(yvals));
yvals.erase(unique(all(yvals)), yvals.end());
for (auto & p : points) {
p.y = getyval(p.y);
}
for (int i = 0; i < n; i++) {
squares[i].l = getyval(squares[i].l);
squares[i].r = getyval(squares[i].r);
}
sort(all(points));
SegmentTree t(size(yvals));
for (auto p : points) {
if (p.query) {
int par = t.query(p.y);
if (par != -1)
smtol[par].insert(q[p.id]);
} else {
if (open[p.id]) {
t.update(squares[p.id].l, squares[p.id].r, parent[p.id]);
} else {
parent[p.id] = t.query(p.y);
if (parent[p.id] != -1)
ch[parent[p.id]].pb(p.id);
t.update(squares[p.id].l, squares[p.id].r, p.id);
open[p.id] = true;
}
}
}
for (int i = 0; i < n; i++) {
if (parent[i] == -1) dfs(i);
}
for (int i = 0; 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... |