#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair< int, int > ii;
const int N = 240005;
const int inf = 1e9 + 5;
int n, m;
vector< int > X, Y, graph[2 * N];
pair < ii, ii > square[2 * N];
pair < ii, int > dart[2 * N];
set< int > st[2 * N];
set< int > :: iterator it;
bool vis[2 * N], used[2 * N];
struct IT {
ii it[4 * N];
IT() {
}
void build_tree(int k, int l, int r) {
if(l == r) {
it[k] = mp(-inf, -inf);
return ;
}
int md = (l + r) >> 1;
build_tree(k << 1, l, md);
build_tree(k << 1 | 1, md + 1, r);
it[k] = max(it[k << 1], it[k << 1 | 1]);
}
void update(int k, int l, int r, int pos, ii val) {
if(pos < l || r < pos) return ;
if(l == pos && pos == r) {
it[k] = val;
return ;
}
int md = (l + r) >> 1;
update(k << 1, l, md, pos, val);
update(k << 1 | 1, md + 1, r, pos, val);
it[k] = max(it[k << 1], it[k << 1 | 1]);
}
ii get(int k, int l, int r, int L, int R) {
if(R < l || r < L || L > R) return mp(-inf, -inf);
if(L <= l && r <= R)
return it[k];
int md = (l + r) >> 1;
return max( get(k << 1, l, md, L, R), get(k << 1 | 1, md + 1, r, L, R) );
}
}tree;
int ans[2 * N];
void dfs(int u, int p) {
//if(vis[u])
//cout << u << " " << vis[u] << "\n";
vis[u] = 1;
for(int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if(v == p || vis[v]) continue;
dfs(v, u);
if(st[u].size() < st[v].size())
st[u].swap(st[v]);
for(it = st[v].begin(); it != st[v].end(); it++)
st[u].insert(*it);
}
ans[u] = st[u].size();
}
vector < pair< ii, ii > > query[2 * N];
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
//freopen("PAINT.inp", "r", stdin);
//freopen("PAINT.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> square[i].fi.fi >> square[i].fi.se >> square[i].se.fi >> square[i].se.se;
if(square[i].fi.fi > square[i].se.fi) swap(square[i].fi.fi, square[i].se.fi);
if(square[i].fi.se > square[i].se.se) swap(square[i].fi.se, square[i].se.se);
X.pb(square[i].fi.fi);
X.pb(square[i].se.fi);
Y.pb(square[i].fi.se);
Y.pb(square[i].se.se);
}
for(int i = 1; i <= m; i++) {
cin >> dart[i].fi.fi >> dart[i].fi.se >> dart[i].se;
X.pb(dart[i].fi.fi); Y.pb(dart[i].fi.se);
}
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
sort(Y.begin(), Y.end());
Y.erase(unique(Y.begin(), Y.end()), Y.end());
for(int i = 1; i <= n; i++) {
int it1 = lower_bound(X.begin(), X.end(), square[i].fi.fi) - X.begin() + 1;
query[it1].pb( mp( mp(square[i].fi.se, square[i].se.se), mp( 1, i ) ) );
it1 = lower_bound(X.begin(), X.end(), square[i].se.fi) - X.begin() + 1;
query[it1].pb( mp( mp(square[i].fi.se, square[i].se.se), mp( -1, i ) ) );
}
for(int i = 1; i <= m; i++) {
int it1 = lower_bound(X.begin(), X.end(), dart[i].fi.fi) - X.begin() + 1;
query[it1].pb( mp( mp( dart[i].fi.se, dart[i].fi.se ), mp( -inf, dart[i].se ) ) );
}
tree.build_tree(1, 1, (int)(Y.size()));
for(int i = 1; i < 2 * N; i++)
sort(query[i].begin(), query[i].end());
for(int i = 1; i < N; i++) {
for(int j = 0; j < query[i].size(); j++) {
pair< ii, ii > type = query[i][j];
int it1 = lower_bound(Y.begin(), Y.end(), type.fi.fi) - Y.begin() + 1;
//cout << "event1" << type.fi.fi << " " << type.fi.se << " " << type.se.fi << " " << type.se.se << "\n";
if(type.se.fi > 0) {
// assert(it1 >= 1 && it1 <= (int)(Y.size()));
tree.update(1, 1, (int)(Y.size()), it1, mp( type.fi.se, type.se.se ) );
}
}
for(int j = 0; j < query[i].size(); j++) {
pair< ii, ii > type = query[i][j];
if(type.se.fi > 0) {
int it1 = lower_bound(Y.begin(), Y.end(), type.fi.fi) - Y.begin() + 1;
int l = 1, r = it1 - 1, md;
while(l < r) {
// cout << i << " " << l << " " << r << "\n";
md = (l + r + 1) >> 1;
if(tree.get(1, 1, (int)(Y.size()), md, it1 - 1).fi >= type.fi.se)
l = md;
else
r = md - 1;
}
ii temp = tree.get(1, 1, (int)(Y.size()), l, it1 - 1);
// cout << temp.fi << " " << temp.se << " " << type.fi.se << " " << type.se.se << "\n";
if(temp.fi >= type.fi.se) {
used[type.se.se] = 1;
graph[temp.se].pb(type.se.se);
}
//if(i >= 226211)
//cout << i << " " << l << " " << it1 << " " << temp.fi << " " << type.se.se << " " << temp.se << " " << type.fi.se << "\n";
}
else if(type.se.fi == -inf) {
int it1 = lower_bound(Y.begin(), Y.end(), type.fi.fi) - Y.begin() + 1;
int l = 1, r = it1, md;
while(l < r) {
md = (l + r + 1) >> 1;
if(tree.get(1, 1, (int)(Y.size()), md, it1).fi >= type.fi.se)
l = md;
else
r = md - 1;
}
//
ii temp = tree.get(1, 1, (int)(Y.size()), l, it1);
if(temp.fi >= type.fi.se) {
st[temp.se].insert(type.se.se);
// cout << "x:" << i << "hihixd" << temp.se << " " << type.se.se << " " << "y:" << temp.fi << " " << type.fi.se << "\n";
}
}
}
for(int j = 0; j < query[i].size(); j++) {
pair< ii, ii > type = query[i][j];
int it1 = lower_bound(Y.begin(), Y.end(), type.fi.fi) - Y.begin() + 1;
if(type.se.fi > 0 || type.se.fi == -inf) continue;
assert(it1 >= 1 && it1 <= (int)(Y.size()));
tree.update(1, 1, (int)(Y.size()), it1, mp( -inf, -inf ) );
}
}
for(int i = 1; i <= n; i++) {
if(!vis[i] && used[i] == 0)
dfs(i, i);
}
for(int i = 1; i <= n; i++)
cout << ans[i] << "\n";
}
Compilation message
plahte.cpp: In function 'void dfs(int, int)':
plahte.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < graph[u].size(); i++) {
~~^~~~~~~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:117:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < query[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~
plahte.cpp:126:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < query[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~
plahte.cpp:167:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < query[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
460 ms |
61104 KB |
Output is correct |
| 2 |
Correct |
467 ms |
61932 KB |
Output is correct |
| 3 |
Correct |
54 ms |
52984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
515 ms |
62220 KB |
Output is correct |
| 2 |
Correct |
513 ms |
62140 KB |
Output is correct |
| 3 |
Correct |
53 ms |
52984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
851 ms |
69140 KB |
Output is correct |
| 2 |
Correct |
941 ms |
66612 KB |
Output is correct |
| 3 |
Correct |
54 ms |
53112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1406 ms |
77504 KB |
Output is correct |
| 2 |
Correct |
1538 ms |
77880 KB |
Output is correct |
| 3 |
Correct |
57 ms |
52984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1468 ms |
76136 KB |
Output is correct |
| 2 |
Correct |
1501 ms |
77192 KB |
Output is correct |
| 3 |
Correct |
59 ms |
53112 KB |
Output is correct |
