Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!
tweet

# Untitled

By: a guest on Jan 24th, 2013  |  syntax: C++  |  size: 2.20 KB  |  views: 217  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. #include <vector>
2. #include <cstdio>
3. #include <cstring>
4. #include <algorithm>
5.
6. using namespace std;
7.
8. #define L(n)((n)<<(1))
9. #define R(n)(L(n)+(1))
10.
11. struct event {
12.    int x, ya, yb, t;
13.    event( int _x, int _ya, int _yb, int _t ) {
14.       x = _x; ya = _ya; yb = _yb; t = _t;
15.    }
16.    friend bool operator<( const event &A, const event &B ) {
17.       return ( A.x == B.x ) ? ( A.t > B.t ) : ( A.x < B.x );
18.    }
19. };
20. struct node {
21.    int cnt, lzy;
22.    node() : cnt( 0 ), lzy( 0 ) {}
23. };
24.
25. vector< event > E;
26. vector< node > Tree;
27. int lo, hi, tlen;
28.
29. void Construct( int n ) {
30.    for( tlen = 1; tlen < n; tlen <<= 1 );
31.    Tree.resize( tlen << 1 );
32. }
33. void update( int x, int y, int v, int n ) {
34.    if( x >= hi || y <= lo ) return;
35.    if( x >= lo && y <= hi ) {
36.       Tree[ n ].lzy += v;
37.       if( Tree[ n ].lzy ) Tree[ n ].cnt = ( y - x );
38.       if( Tree[ n ].lzy < 1 ) {
39.          if( n >= tlen ) Tree[ n ].cnt = 0;
40.          else Tree[ n ].cnt = Tree[ L( n ) ].cnt + Tree[ R( n ) ].cnt;
41.       }
42.       return;
43.    }
44.
45.    update( x, ( x + y )>>1, v, L( n ) );
46.    update( ( x + y )>>1, y, v, R( n ) );
47.
48.    if( Tree[ n ].lzy < 1 )
49.       Tree[ n ].cnt = Tree[ L( n ) ].cnt + Tree[ R( n ) ].cnt;
50. }
51.
52. void Update( int x, int y, int v ) {
53.    lo = x; hi = y;
54.    update( 0, tlen, v, 1 );
55. }
56. int query( int x, int y, int n ) {
57.    if( x >= hi || y <= lo ) return 0;
58.    if( x >= lo && y <= hi ) return Tree[ n ].cnt;
59.    if( Tree[ n ].lzy ) return min( y, hi ) - max( x, lo );
60.
61.    return query( x, ( x + y )>>1, L( n ) ) +
62.           query( ( x + y )>>1, y, R( n ) );
63. }
64. int Query() {
65.    lo = 0; hi = 30005;
66.    return query( 0, tlen, 1 );
67. }
68.
69. int main( void )
70. {
71.    int N; scanf( "%d", &N );
72.    for( int i = 0; i < N; ++i ) {
73.       int xa, ya, xb, yb;
74.       scanf( "%d%d%d%d", &xa, &ya, &xb, &yb );
75.       E.push_back( event( xa, ya, yb, +1 ) );
76.       E.push_back( event( xb, ya, yb, -1 ) );
77.    }
78.
79.    Construct( 30005 );
80.
81.    sort( E.begin(), E.end() );
82.    int last = 0, sol = 0;
83.
84.    for( int i = 0; i < E.size(); ++i ) {
85.       sol += Query()*( E[i].x - last );
86.       Update( E[i].ya, E[i].yb, E[i].t );
87.       last = E[i].x;
88.    }
89.
90.    printf( "%d\n", sol );
91.
92.    return 0;
93. }
clone this paste RAW Paste Data
Top