| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1124523 | FubuGold | Plahte (COCI17_plahte) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
struct Query {
int x,type,l,r,id;
Query() {};
Query(int _x,int _t,int _l,int _r,int _id) :
x(_x),type(_t),l(_l),r(_r),id(_id) {}
bool operator < (Query &qr) const {
if (x == qr.x) return type < qr.type;
return x < qr.x;
}
};
vector<Query> qr;
set<pair<int,int>> st;
int col_inp[MAXN+1];
int pa[MAXN+1];
bool re_add[MAXN+1];
vector<int> adj[MAXN+1];
set<int> col[MAXN+1];
int ans[MAXN+1];
int n,m;
void dfs(int u) {
int mx_v = -1;
int mx_sz = 0;
for (int i=0;i<adj[u].size();i++) {
int v = adj[u][i];
dfs(v);
if (col[v].size() > mx_sz) {
mx_v = v;
mx_sz = col[v].size();
}
}
if (mx_v != -1) {
col[u].swap(col[mx_v]);
for (int i=0;i<adj[u].size();i++) {
int v = adj[u][i];
for (set<int>::iterator it = col[v].begin();it != col[v].end();it++) {
col[u].insert(*it);
}
col[v].clear();
}
}
ans[u] = col[u].size();
}
signed main() {
// freopen("LOANGMUC.inp","r",stdin);
// freopen("LOANGMUC.out","w",stdout);
cin.tie(0) -> sync_with_stdio(0);
cin >> n >> m;
for (int i=1;i<=n;i++) {
int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
qr.push_back(Query(x1,0,y1,y2,i));
qr.push_back(Query(x2,2,y1,y2,i));
}
for (int i=1;i<=m;i++) {
int x,y; cin >> x >> y >> col_inp[i];
qr.push_back(Query(x,1,y,y,i));
}
sort(qr.begin(),qr.end());
st.insert(make_pair((int)1e9+1,0));
for (int i=0;i<qr.size();i++) {
int id = qr[i].id;
if (qr[i].type == 0) {
int l = qr[i].l, r = qr[i].r;
set<pair<int,int>>::iterator it = st.lower_bound(make_pair(r,-1));
adj[it->second].push_back(id);
pa[id] = it->second;
if (it->first == r) {
re_add[id] = 1;
st.erase(it);
}
st.insert(make_pair(r,id));
st.insert(make_pair(l-1,pa[id]));
}
else if (qr[i].type == 2) {
int r = qr[i].r;
set<pair<int,int>>::iterator it = st.lower_bound(make_pair(r,-1));
set<pair<int,int>>::iterator tmp = it;
it++;
st.erase(tmp);
if (re_add[id]) {
it = st.insert(make_pair(r,pa[id]));
}
while (true) {
tmp = it;
if (tmp == st.begin()) break;
tmp--;
if (tmp->second != pa[id]) break;
st.erase(tmp);
}
}
else {
int p = qr[i].l;
set<pair<int,int>>::iterator it = st.lower_bound(make_pair(p,-1));
// for (auto x : st) cerr << "why " << x.first << ' ' << x.second << '\n';
col[it->second].insert(col_inp[id]);
}
}
dfs(0);
for (int i=1;i<=n;i++) cout << ans[i] << '\n';
return 0;
}