# IOI 1998 Picture ( Scanning Line, Segment Tree )

PEG Judge - IOI '98 - Picture

The first line of the input contains the number of rectangles (0 ≤ number of rectangles < 5000) pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate. All coordinates are in the inclusive range [−10000, 10000] and any existing rectangle has a positive area.

O( N lg N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000;

int N;
int L[ MAXN ], D[ MAXN ], R[ MAXN ], U[ MAXN ];

struct segt{
int lb, rb;
int cov;
int cov_len;
segt *lc, *rc;
segt(){}
segt( int ll, int rr ){
lb = ll, rb = rr;
cov = cov_len = 0;
lc = rc = NULL;
}
void pull(){
if( cov ){
cov_len = rb - lb;
return;
}
cov_len = ( lc ? lc->cov_len : 0 ) + ( rc ? rc->cov_len : 0 );
}
} *root;

void update( segt *t, int ql, int qr, int v ){
if( qr <= t->lb or t->rb <= ql ) return;
if( ql <= t->lb and t->rb <= qr ){
t->cov += v;
t->pull();
return;
}
int mid = t->lb + t->rb >> 1;
if( not t->lc ){
t->lc = new segt( t->lb, mid );
}
update( t->lc, ql, qr, v );
if( not t->rc ){
t->rc = new segt( mid, t->rb );
}
update( t->rc, ql, qr, v );
t->pull();
}

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N; ++i ){
cin >> L[ i ] >> D[ i ] >> R[ i ] >> U[ i ];
}
long long ans = 0;
{
root = new segt( *min_element( L, L + N ), *max_element( R, R + N ) );
vector< tuple< int, int, int, int > > event;
for( int i = 0; i < N; ++i ){
event.emplace_back( D[ i ], 0, L[ i ], R[ i ] ); // 0 for in to prevent
event.emplace_back( U[ i ], 1, L[ i ], R[ i ] ); // problems regarding overlap
}
sort( event.begin(), event.end() );
for( int i = 0, prev_len = 0; i < 2 * N; ++i ){
int y, t, ll, rr; tie( y, t, ll, rr ) = event[ i ];
update( root, ll, rr, t ? -1 : 1 );
ans += abs( root->cov_len - prev_len );
prev_len = root->cov_len;
}
}
{
root = new segt( *min_element( D, D + N ), *max_element( U, U + N ) );
vector< tuple< int, int, int, int > > event;
for( int i = 0; i < N; ++i ){
event.emplace_back( L[ i ], 0, D[ i ], U[ i ] ); // 0 for in to prevent
event.emplace_back( R[ i ], 1, D[ i ], U[ i ] ); // problems regarding overlap
}
sort( event.begin(), event.end() );
for( int i = 0, prev_len = 0; i < 2 * N; ++i ){
int y, t, ll, rr; tie( y, t, ll, rr ) = event[ i ];
update( root, ll, rr, t ? -1 : 1 );
ans += abs( root->cov_len - prev_len );
prev_len = root->cov_len;
}
}
cout << ans << "\n";
return 0;
}
```

.

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000;

int N;
int L[ MAXN ], D[ MAXN ], R[ MAXN ], U[ MAXN ];

struct segt{
int lb, rb;
int cov;
int cov_len;
bool cov_l, cov_r;
int cov_cnt;
segt *lc, *rc;
segt(){}
segt( int ll, int rr ){
lb = ll, rb = rr;
cov = cov_len = cov_l = cov_r = cov_cnt = 0;
lc = rc = NULL;
}
void pull(){
if( cov ){
cov_len = rb - lb;
cov_l = cov_r = cov_cnt = 1;
return;
}
cov_len = ( lc ? lc->cov_len : 0 ) + ( rc ? rc->cov_len : 0 );
cov_l = lc ? lc->cov_l : 0;
cov_r = rc ? rc->cov_r : 0;
cov_cnt = ( lc ? lc->cov_cnt : 0 ) + ( rc ? rc->cov_cnt : 0 ) - ( lc and rc and lc->cov_r and rc->cov_l );
}
} *root;

void update( segt *t, int ql, int qr, int v ){
if( qr <= t->lb or t->rb <= ql ) return;
if( ql <= t->lb and t->rb <= qr ){
t->cov += v;
t->pull();
return;
}
int mid = t->lb + t->rb >> 1;
if( not t->lc ){
t->lc = new segt( t->lb, mid );
}
update( t->lc, ql, qr, v );
if( not t->rc ){
t->rc = new segt( mid, t->rb );
}
update( t->rc, ql, qr, v );
t->pull();
}

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N; ++i ){
cin >> L[ i ] >> D[ i ] >> R[ i ] >> U[ i ];
}
long long ans = 0;
{
root = new segt( *min_element( L, L + N ), *max_element( R, R + N ) );
vector< tuple< int, int, int, int > > event;
for( int i = 0; i < N; ++i ){
event.emplace_back( D[ i ], 0, L[ i ], R[ i ] ); // 0 for in to prevent
event.emplace_back( U[ i ], 1, L[ i ], R[ i ] ); // problems regarding overlap
}
sort( event.begin(), event.end() );
for( int i = 0, prev_len = 0, prev_hei = 0; i < 2 * N; ++i ){
int y, t, ll, rr; tie( y, t, ll, rr ) = event[ i ];
ans += 2LL * root->cov_cnt * ( y - prev_hei );
update( root, ll, rr, t ? -1 : 1 );
ans += abs( root->cov_len - prev_len );
prev_len = root->cov_len;
prev_hei = y;
}
}
cout << ans << "\n";
return 0;
}
```