#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double Lf;
typedef pair<int, int> pii;
const int maxn = 1.5e5 + 5;
const int maxm = 1.5e5 + 5;
const int maxv = maxn + maxm;
int n, m, tot;
class Rectangle{
public:
ll a, b, c, d;
} rec[maxn];
class Ink{
public:
ll x, y;
int k;
} ink[maxm];
class Event{
public:
ll t;
int id;
Event(){}
Event(ll t_, int id_): t(t_), id(id_){}
inline bool operator < (const Event &oth)const{
if(t != oth.t)
return (t < oth.t);
int tp1 = (id < 0 ? 2 : (id > n ? 1 : 0)), tp2 = (oth.id < 0 ? 2 : (oth.id > n ? 1 : 0));
return tp1 < tp2;
}
} ;
vector<Event> evn;
class SegmentTree{
private:
inline void pushDown(int x){
if(dat[x])
dat[x << 1] = dat[x << 1 | 1] = dat[x], dat[x] = 0;
return;
}
public:
static const int siz = 1048576;
int dat[siz << 1];
inline int size(){ return siz; }
inline void init(){ memset(dat, -1, sizeof(dat)); }
inline void update(int x, int l, int r, int s, int t, int k){
if(l >= s && r <= t){
dat[x] = k;
return;
}
int md = l + r >> 1;
pushDown(x);
if(s <= md)
update(x << 1, l, md, s, t, k);
if(t > md)
update(x << 1 | 1, md + 1, r, s, t, k);
return;
}
inline int query(int x, int l, int r, int y){
if(l == r)
return dat[x];
int md = l + r >> 1;
pushDown(x);
if(y <= md)
return query(x << 1, l, md, y);
return query(x << 1 | 1, md + 1, r, y);
}
} seg;
int id[maxv], ans[maxn], fa[maxv];
vector<ll> vy;
vector<int> g[maxv];
set<int> col[maxv];
inline int pos(ll x){ return lower_bound(vy.begin(), vy.end(), x) - vy.begin(); }
inline void insert(int i){
int l = pos(rec[i].b), r = pos(rec[i].d);
int res = seg.query(1, 0, seg.size() - 1, l);
if(res)
fa[i] = res;
seg.update(1, 0, seg.size() - 1, l, r, i);
return;
}
inline void erase(int i){
int l = pos(rec[i].b), r = pos(rec[i].d);
seg.update(1, 0, seg.size() - 1, l, r, fa[i]);
return;
}
inline void paint(int i){
int y = pos(ink[i].y);
int res = seg.query(1, 0, seg.size() - 1, y);
fa[i + n] = res;
return;
}
inline void merge(int u, int v){
if(col[id[u]].size() < col[id[v]].size())
swap(id[u], id[v]);
for(set<int>::iterator it = col[id[v]].begin(); it != col[id[v]].end(); ++it)
col[id[u]].insert(*it);
return;
}
inline void dfs(int u){
id[u] = tot++;
if(u > n){
col[id[u]].insert(ink[u - n].k);
return;
}
FOR(i, 0, g[u].size()){
int v = g[u][i];
dfs(v);
merge(u, v);
}
ans[u] = col[id[u]].size();
return;
}
int main(){
// freopen("b.in", "r", stdin);
// freopen("b.out", "w", stdout);
scanf("%d%d", &n, &m);
REP(i, 1, n){
scanf("%lld%lld%lld%lld", &rec[i].a, &rec[i].b, &rec[i].c, &rec[i].d);
evn.PB(Event(rec[i].a, i));
evn.PB(Event(rec[i].c, -i));
vy.PB(rec[i].b);
vy.PB(rec[i].d);
}
REP(i, 1, m){
scanf("%lld%lld%d", &ink[i].x, &ink[i].y, &ink[i].k);
evn.PB(Event(ink[i].x, n + i));
vy.PB(ink[i].y);
}
sort(vy.begin(), vy.end());
vy.erase(unique(vy.begin(), vy.end()), vy.end());
sort(evn.begin(), evn.end());
memset(fa, -1, sizeof(fa));
seg.init();
for(int i = 0, j; i < evn.size(); i = j){
for(j = i; j < evn.size() && evn[j].t == evn[i].t; ++j){
if(evn[j].id > n)
paint(evn[j].id - n);
else if(evn[j].id > 0)
insert(evn[j].id);
else
erase(-evn[j].id);
}
}
REP(i, 1, n + m) if(~fa[i])
g[fa[i]].PB(i);
REP(i, 1, n + m) if(!~fa[i])
dfs(i);
REP(i, 1, n)
printf("%d\n", ans[i]);
return 0;
}
Compilation message
plahte.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
plahte.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int md = l + r >> 1;
| ~~^~~
plahte.cpp: In member function 'int SegmentTree::query(int, int, int, int)':
plahte.cpp:78:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | int md = l + r >> 1;
| ~~^~~
plahte.cpp: In function 'void dfs(int)':
plahte.cpp:5:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define FOR(i, x, y) for(int i = (x); i < (y); ++i)
| ^
plahte.cpp:129:2: note: in expansion of macro 'FOR'
129 | FOR(i, 0, g[u].size()){
| ^~~
plahte.cpp: In function 'int main()':
plahte.cpp:167:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
167 | for(int i = 0, j; i < evn.size(); i = j){
| ~~^~~~~~~~~~~~
plahte.cpp:168:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | for(j = i; j < evn.size() && evn[j].t == evn[i].t; ++j){
| ~~^~~~~~~~~~~~
plahte.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
143 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
plahte.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
146 | scanf("%lld%lld%lld%lld", &rec[i].a, &rec[i].b, &rec[i].c, &rec[i].d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
154 | scanf("%lld%lld%d", &ink[i].x, &ink[i].y, &ink[i].k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
40412 KB |
Output is correct |
| 2 |
Correct |
122 ms |
41180 KB |
Output is correct |
| 3 |
Correct |
20 ms |
30828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
128 ms |
41692 KB |
Output is correct |
| 2 |
Correct |
134 ms |
41308 KB |
Output is correct |
| 3 |
Correct |
22 ms |
30828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
50004 KB |
Output is correct |
| 2 |
Correct |
214 ms |
47700 KB |
Output is correct |
| 3 |
Correct |
20 ms |
30956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
364 ms |
61780 KB |
Output is correct |
| 2 |
Correct |
392 ms |
58708 KB |
Output is correct |
| 3 |
Correct |
20 ms |
30828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
364 ms |
59732 KB |
Output is correct |
| 2 |
Correct |
356 ms |
58176 KB |
Output is correct |
| 3 |
Correct |
19 ms |
30956 KB |
Output is correct |
