#include <bits/stdc++.h>
using namespace std;
#define ln '\n'
#define all(x) x.begin(), x.end()
#define forn(i, n) for(int i = 0; i < n; i++)
#define forab(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define sz(x) int(x.size())
#define rforn(i, n) for (int i = n-1; i >= 0; --i)
#define form(i, n, m, x) for (int i = n; i < m; i += x)
#define rform(i, n, m, x) for (int i = n; i >= m; i -= x)
#ifdef LOCAL
#include "debug.cpp"
#else
#define dbg(...)
#endif
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vll;
template<typename T>
void print(T *a, int l, int r){
cout << "===> [";
for(int i = l; i < r; i++){
if(i == r - 1) cout << (a[i]) << "]\n";
else cout << a[i] << ", ";
}
}
template<typename T>
struct STree {
int n;
vector<T> st, lazy;
T neutro = T(0);
STree(int m) {
n = m;
st.resize(n * 4);
lazy.resize(n * 4);
}
STree(vector<T> &a) {
n = sz(a);
st.resize(n * 4);
lazy.resize(n * 4, -1);
build(1, 0, n - 1, a);
}
T oper(T a, T b) {
return max(a, b);
}
void build(int v, int tl, int tr, vector<T> &a) {
if(tl == tr) {
st[v] = a[tl];
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm, a);
build(v * 2 + 1, tm + 1, tr, a);
st[v] = oper(st[v * 2], st[v * 2 + 1]);
}
void push(int v, int tl, int tr) {
if (lazy[v] == -1) return;
st[v] = lazy[v];
if (tl != tr) {
lazy[v * 2] = lazy[v];
lazy[v * 2 + 1] = lazy[v];
}
lazy[v] = -1;
}
void upd(int v, int tl, int tr, int l, int r, T val) {
push(v, tl, tr);
if(tr < l || tl > r) return;
if (tl >= l && tr <= r) {
lazy[v] = val;
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
upd(v * 2, tl, tm, l, r, val);
upd(v * 2 + 1, tm + 1, tr, l, r, val);
st[v] = oper(st[v * 2], st[v * 2 + 1]);
}
T query(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if(tl > r || tr < l) return neutro;
if (l <= tl && tr <= r) return st[v];
int tm = (tl + tr) / 2;
return oper(query(v * 2, tl, tm, l, r), query(v * 2 + 1, tm + 1, tr, l, r));
}
void upd(int l, int r, T val) {
upd(1, 0, n - 1, l, r, val);
}
T query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
};
struct event {
int x, y, id, t;
bool operator < (event &o) const {
if(x == o.x) return t < o.t;
return x < o.x;
}
};
int n, m;
const int MAXN = 80005;
vector<array<int, 4>> rec(MAXN);
vector<array<int, 3>> pts(MAXN);
int parent[MAXN];
vi g[MAXN];
bool vis[MAXN];
int ans[MAXN];
set<int> dsu[MAXN];
vector<event> order;
vi compression;
int get_id(int x){
return lower_bound(all(compression), x) - compression.begin();
}
set<int> dfs(int u, int p){
if(vis[u]) return {};
vis[u] = 1;
set<int> a = dsu[u];
for(int v: g[u]){
if(!vis[v]){
set<int> b = dfs(v, u);
if(sz(a) < sz(b)) swap(a, b);
for(int i: b){
a.insert(i);
}
}
}
ans[u] = sz(a);
return a;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
cin >> n >> m;
forab(i, 1, n + 1){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
rec[i] = {x1, y1, x2, y2};
order.pb({x1, y1, i, 0});
order.pb({x2, y2, i, 2});
compression.pb(y1);
compression.pb(y2);
}
forab(i, 1, m + 1){
int x, y, c;
cin >> x >> y >> c;
pts[i] = {x, y, c};
order.pb({x, y, i, 1});
compression.pb(y);
}
sort(all(order));
sort(all(compression));
compression.erase(unique(all(compression)), compression.end());
vi aux(sz(compression) + 1, 0);
forab(i, 1, n + 1) parent[i] = 0;
STree<int> st(aux);
for(auto [x, y, i, type] : order){
if(type == 0){
//rectangulo inicio
auto [x1, y1, x2, y2] = rec[i];
int l = get_id(y1);
int r = get_id(y2);
parent[i] = st.query(l, r);
st.upd(l, r, i);
}else if(type == 1){
//punto
int idx = get_id(y);
int p = st.query(idx, idx);
dsu[p].insert(pts[i][2]);
}else{
//rectangulo fin
auto [x1, y1, x2, y2] = rec[i];
int l = get_id(y1);
int r = get_id(y2);
st.upd(l, r, parent[i]);
}
}
forab(i, 1, n + 1){
g[parent[i]].pb(i);
g[i].pb(parent[i]);
}
/*
forab(i, 1, n + 1){
dbg(i, parent[i]);
}
*/
dfs(0, 0);
//cout << "2" << ln;
forab(i, 1, n + 1) {
cout << ans[i] << ln;
}
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... |