#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 = 80005;
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[8 * 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) {
vis[u] = 1;
for(int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if(v == p) 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 < 2 * 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)
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) {
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);
}
}
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;
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:65: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:115:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < query[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~
plahte.cpp:122:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < query[i].size(); j++) {
~~^~~~~~~~~~~~~~~~~
plahte.cpp:158: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 |
419 ms |
28652 KB |
Output is correct |
| 2 |
Correct |
428 ms |
29548 KB |
Output is correct |
| 3 |
Correct |
21 ms |
20472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
458 ms |
29932 KB |
Output is correct |
| 2 |
Correct |
474 ms |
29924 KB |
Output is correct |
| 3 |
Correct |
23 ms |
20472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
841 ms |
38484 KB |
Output is correct |
| 2 |
Correct |
850 ms |
34864 KB |
Output is correct |
| 3 |
Correct |
21 ms |
20344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1210 ms |
48832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1183 ms |
46844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
