#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;
int id[maxv], ans[maxn], fa[maxv];
vector<int> vk;
vector<int> g[maxv];
set<pair<pair<ll, ll>, int> > s;
set<int> col[maxv];
inline void insert(int i){
// printf("insert (%d %d) %d\n", rec[i].b, rec[i].d, i);
set<pair<pair<ll, ll>, int> >::iterator it = s.lower_bound(MP(MP(rec[i].b, 0), 0));
if(it == s.begin()){
s.insert(MP(MP(rec[i].b, rec[i].d), i));
return;
}
--it;
int j = it -> snd;
if((it -> fst).snd > rec[i].b){
fa[i] = j;
pair<pair<ll, ll>, int> lit = MP(MP((it -> fst).fst, rec[i].b), it -> snd),
rit = MP(MP(rec[i].d, (it -> fst).snd), it -> snd);
s.erase(it);
s.insert(lit);
s.insert(rit);
}
s.insert(MP(MP(rec[i].b, rec[i].d), i));
return;
}
inline void erase(int i){
// printf("erase (%d %d) %d\n", rec[i].b, rec[i].d, i);
set<pair<pair<ll, ll>, int> >::iterator it = s.lower_bound(MP(MP(rec[i].b, rec[i].d), i));
if(~fa[i]){
set<pair<pair<ll, ll>, int> >::iterator lit = it, rit = it;
--lit, ++rit;
pair<pair<ll, ll>, int> nit = MP(MP((lit -> fst).fst, (rit -> fst).snd), fa[i]);
s.erase(lit), s.erase(rit);
s.insert(nit);
}
s.erase(it);
return;
}
inline void paint(int i){
// printf("paint y = %d i = %d\n", ink[i].y, i);
set<pair<pair<ll, ll>, int> >::iterator it = s.upper_bound(MP(MP(ink[i].y, ink[i].y), 0));
if(it == s.begin())
return;
--it;
if((it -> fst).snd >= ink[i].y)
fa[i + n] = (it -> snd);
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(){
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));
}
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));
vk.PB(ink[i].k);
}
sort(vk.begin(), vk.end());
REP(i, 1, m)
ink[i].k = lower_bound(vk.begin(), vk.end(), ink[i].k) - vk.begin();
sort(evn.begin(), evn.end());
memset(fa, -1, sizeof(fa));
// FOR(i, 0, evn.size())
// printf("t = %d id = %d\n", evn[i].t, evn[i].id);
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 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:116:2: note: in expansion of macro 'FOR'
116 | FOR(i, 0, g[u].size()){
| ^~~
plahte.cpp: In function 'int main()':
plahte.cpp:151:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for(int i = 0, j; i < evn.size(); i = j){
| ~~^~~~~~~~~~~~
plahte.cpp:152:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for(j = i; j < evn.size() && evn[j].t == evn[i].t; ++j){
| ~~^~~~~~~~~~~~
plahte.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
127 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
plahte.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
130 | scanf("%lld%lld%lld%lld", &rec[i].a, &rec[i].b, &rec[i].c, &rec[i].d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
136 | scanf("%lld%lld%d", &ink[i].x, &ink[i].y, &ink[i].k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
31964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
32860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
218 ms |
40788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
335 ms |
51388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
336 ms |
49340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
