#include<bits/stdc++.h>
#define Nst (nod<<1)
#define Ndr ((nod<<1)|1)
using namespace std;
const int DIM = 8e4 + 5;
int N, M;
struct event{
int tip, pos, x, y, ind;
};
vector<event> arr;
vector<int> Norm, edge[DIM];
set<int> col[DIM];
int t[DIM], wh_set[DIM], ans[DIM];
struct aint{
bool lazy;
int val;
} A[4 * DIM];
void build( int nod, int st, int dr ){
A[nod].lazy = false;
A[nod].val = 1;
if( st != dr ){
int mid = ( st + dr ) >> 1;
build( Nst, st, mid + 0 );
build( Ndr, mid + 1, dr );
}
}
inline void update_lazy( int nod, int st, int dr ){
if( A[nod].lazy == false )
return;
A[nod].lazy = false;
if( st != dr ){
A[Nst].lazy = A[Ndr].lazy = true;
A[Nst].val = A[Ndr].val = A[nod].val;
}
}
void update( int nod, int st, int dr, int a, int b, int x ){
update_lazy( nod, st, dr );
if( a <= st && dr <= b ){
A[nod].lazy = true;
A[nod].val = x;
}else{
int mid = ( st + dr ) >> 1;
if( a <= mid )
update( Nst, st, mid + 0, a, b, x );
if( b > mid )
update( Ndr, mid + 1, dr, a, b, x );
}
}
int query( int nod, int st, int dr, int p ){
update_lazy( nod, st, dr );
if( st == dr ){
return A[nod].val;
}else{
int mid = ( st + dr ) >> 1;
if( p <= mid )
return query( Nst, st, mid + 0, p );
else
return query( Ndr, mid + 1, dr, p );
}
}
inline bool cmp( event a, event b ){
if( a.pos == b.pos )
return a.tip < b.tip;
return a.pos < b.pos;
}
inline int getp( int x ){
int st = 0, dr = Norm.size() - 1;
while( st <= dr ){
int mid = ( st + dr ) >> 1;
if( Norm[mid] <= x )
st = mid + 1;
else
dr = mid - 1;
}
return dr + 1;
}
void dfs( int v ){
wh_set[v] = v;
if( edge[v].empty() ){
ans[v] = col[ wh_set[v] ].size();
return;
}
for( auto son : edge[v] )
dfs( son );
int heavy_son = v;
for( auto son : edge[v] ){
if( col[ wh_set[son] ] > col[ wh_set[heavy_son] ] )
heavy_son = son;
}
wh_set[v] = heavy_son;
for( auto son : edge[v] ){
if( son != wh_set[v] ){
for( set<int>::iterator it = col[ wh_set[son] ].begin(); it != col[ wh_set[son] ].end(); it++ )
col[ wh_set[v] ].insert( (*it) );
}
}
if( wh_set[v] != v )
for( set<int>::iterator it = col[v].begin(); it != col[v].end(); it++ )
col[ wh_set[v] ].insert( (*it) );
ans[v] = col[ wh_set[v] ].size();
return;
}
int main(){
cin >> N >> M;
for( int i = 1; i <= N; i++ ){
int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
arr.push_back( {1, x1, y1, y2, i + 1} );
arr.push_back( {3, x2, y1, y2, i + 1} );
Norm.push_back( y1 );
Norm.push_back( y2 );
}
for( int i = 1; i <= M; i++ ){
int x, y, c; cin >> x >> y >> c;
arr.push_back( {2, x, y, y, c} );
Norm.push_back( y );
}
sort( Norm.begin(), Norm.end() );
Norm.resize( distance( Norm.begin(), unique( Norm.begin() , Norm.end() ) ) );
sort( arr.begin(), arr.end(), cmp );
int n = N + 1;
N = Norm.size();
build( 1, 1, N );
for( int i = 0; i < arr.size(); i++ ){
event curr = arr[i];
if( arr[i].tip == 1 ){
int p1 = getp( arr[i].x ), p2 = getp( arr[i].y );
t[ arr[i].ind ] = query( 1, 1, N, p1 );
edge[ t[ arr[i].ind ] ].push_back( arr[i].ind );
update( 1, 1, N, p1, p2, arr[i].ind );
}
if( arr[i].tip == 2 ){
int nod = query( 1, 1, N, getp( arr[i].x ) );
col[nod].insert( arr[i].ind );
}
if( arr[i].tip == 3 ){
int p1 = getp( arr[i].x ), p2 = getp( arr[i].y );
update( 1, 1, N, p1, p2, t[ arr[i].ind ] );
}
}
dfs( 1 );
for( int i = 2; i <= n; i++ )
cout << ans[i] << "\n";
return 0;
}
Compilation message
plahte.cpp: In function 'int main()':
plahte.cpp:147:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for( int i = 0; i < arr.size(); i++ ){
~~^~~~~~~~~~~~
plahte.cpp:148:15: warning: variable 'curr' set but not used [-Wunused-but-set-variable]
event curr = arr[i];
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
228 ms |
19332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
255 ms |
19520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
319 ms |
31168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
493 ms |
37104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
491 ms |
37120 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
