#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
#ifndef LOAL
const int mxN = 1e5+1, oo = 1e9, ptwo = 1<<19;
#else
const int mxN = 1e2+1, oo = 1e9, ptwo = 1<<8;
#endif
unordered_set<int> colours[mxN];
int ans[mxN];
vi kid[mxN];
bitset<mxN> notroot;
void dfs(int at) {
for(int to:kid[at]) {
dfs(to);
if(colours[to].size()>colours[at].size()) {
swap(colours[at],colours[to]);
}
for(auto c: colours[to]) colours[at].insert(c);
}
ans[at] = colours[at].size();
}
struct tourtree {
stack<int> seg[2*ptwo] = {};
void put(int l, int r, int i) {
for(l+=ptwo,r+=ptwo;l>0 and l<r;l/=2,r/=2) {
if(l&1) seg[l++].push(i);
if(r&1) seg[--r].push(i);
}
}
void take(int l, int r) {
for(l+=ptwo,r+=ptwo;l>0 and l<r;l/=2,r/=2) {
if(l&1) seg[l++].pop();
if(r&1) seg[--r].pop();
}
}
int get(int y) {
int res = -1;
for(y+=ptwo;y>0;y/=2) {
if(!seg[y].empty())
res = max(res,seg[y].top());
}
return res;
}
} *seg = new tourtree();
vi coord; // coord compression on y axis
int real(int i) {
return lower_bound(all(coord),i)-coord.begin();
}
struct event {
int x,y1,y2=-oo,i;
bool end = false, sheet=true;
event() {}
event(int X,int Y1, int Y2, int I, bool End) : x(X),y1(Y1),y2(Y2),i(I) {
if(End) {
coord.push_back(y1);
coord.push_back(y2);
end=true;
}
}
bool operator<(const event& o) const {
if(x==o.x) {
if(sheet==o.sheet) return end>o.end;
else if(sheet) return !end;
else return o.end;
}
return x<o.x;
}
};
int main() {
int n,m; cin >> n >> m;
coord.reserve(2*n+2); coord.push_back(oo+100); coord.push_back(-1);
vector<event> es(2*n+m);
for(int i=0;i<n;++i) {
auto& e1 = es[2*i],&e2 = es[2*i+1];
int a,b,c,d; cin >> a >> b >> c >> d;
e1 = event(a,b,d,i,false);
e2 = event(c,b,d,i,true);
}
for(int i=2*n;i<2*n+m;++i) {
auto& b = es[i];
cin >> b.x >> b.y1 >> b.i;
b.sheet = false;
coord.push_back(b.y1);
}
sort(all(coord));
coord.erase(unique(all(coord)),coord.end());
sort(all(es));
int level = 0;
for(auto& e : es) {
auto getsheet = [&](int y) {
int j = seg->get(y);
if(j==-1) return -1;
return es[j].i;
};
if(e.sheet) {
e.y1 = real(e.y1);
e.y2 = real(e.y2);
if(e.end) {
// remove sheet from tour tree
seg->take(e.y1,e.y2+1);
} else {
int par = getsheet(e.y1);
if(par!=-1){
kid[par].push_back(e.i);
notroot[e.i] = true;
}
seg->put(e.y1,e.y2+1,level);
}
} else {
// shoot paintball
int realy = real(e.y1),target=-1;
target = getsheet(realy);
if(target!=-1)
colours[target].insert(e.i);
}
level++;
}
for(int i=0;i<n;++i) {
if(!notroot[i]) dfs(i);
}
for(int i=0;i<n;++i) {
cout << ans[i] << '\n';
}
}
Compilation message
Compilation timeout while compiling plahte
