Pastebin launched a little side project called HostCabi.net, check it out ;-)Don't like ads? PRO users don't see any ads ;-)
Guest

Untitled

By: a guest on Jan 24th, 2013  |  syntax: C++  |  size: 2.20 KB  |  hits: 131  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
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. }