Cod sursa(job #828620)

Utilizator veleanduAlex Velea veleandu Data 3 decembrie 2012 23:47:33
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
 
    #define MaxChar 1000000
    #define verf ( (++CharB==MaxChar) ? ( cin.read(Buffer,MaxChar),CharB=0 ) : (1) )
     
    long CharB=MaxChar-1;
    char Buffer [ MaxChar ];
     
    void cit ( int &a ){
        bool ok=0;
        for ( ; !( (Buffer[ CharB ]>='0' && Buffer[ CharB ]<='9') || ( Buffer[ CharB ] == '-' ) ); verf )
            ;
        if ( Buffer[ CharB ] == '-' ){
            verf;
            ok=1;
        }
        for ( a=0; (Buffer[ CharB ]>='0' && Buffer[ CharB ]<='9'); a*=10,a+=( Buffer[ CharB ]-'0'), verf )
            ;
        if ( ok ){
            a=-a;
        }
    }
 
 
 
    #define max_n 20000
    #define max_m 120000
    #define INF 2000000005
    #define pb push_back
 
 
    vector<int> El;
 
    struct point {
        int x,y,nr; 
    } Po[max_n],Ta[4*max_m];
 
    bool mysort ( point a, point b ){
        return a.y < b.y;
    }
 
    int Rez[4*max_m];
    int n,m,i,j,rez;
 
    int a,b,c,d,task;
    int Aib[6*max_m];
 
 
    void add ( int ind, int val ){
        for ( ; ind < 6*max_m; ind+=(ind)&(-ind) )
            Aib[ind]+=val;
    }
    int query ( int ind ){
        int rez=0;
        for ( ; ind; ind-=(ind)&(-ind) )
            rez+=Aib[ind];
        return rez;
    }
 
    int bs ( int val ){
        int ind=(1<<19),rez=0;
        for ( ; ind; ind>>=1 ){
            if ( rez+ind < int(El.size()) ){
                if ( El[ ind+rez ] <= val ){
                    rez+=ind;
                }
            }
        }
        return rez;
    }
 
int main(){
    freopen ("zoo.in","r",stdin);
    freopen ("zoo.out","w",stdout);
    verf;
//  scanf ("%d", &n );
    cit(n);
    for ( i=1; i<=n; i++ ){
//      scanf ("%d %d", &Po[i].x, &Po[i].y );
        cit( Po[i].x );
        cit( Po[i].y );
        El.pb( Po[i].x );
        El.pb( Po[i].y );
    }
    El.pb( INF );
    El.pb( -INF );
    El.pb( -INF );
    El.pb( -INF );
    Po[n+1].x=INF;
    Po[n+1].y=INF;
 
//  scanf ("%d", &m );
    cit(m);
    for ( i=1; i<=m; i++ ){
//      scanf ("%d %d %d %d", &a, &b, &c, &d );
        cit(a);
        cit(b);
        cit(c);
        cit(d);
 
        a--;
        b--;
 
        El.pb ( a );
        El.pb ( b );
        El.pb ( c );
        El.pb ( d );
 
        ++task;
        Ta[task].x = a;
        Ta[task].y = b;
        Ta[task].nr = task;
 
        ++task;
        Ta[task].x = c;
        Ta[task].y = d;
        Ta[task].nr = task;
 
        ++task;
        Ta[task].x = a;
        Ta[task].y = d;
        Ta[task].nr = task;
 
        ++task;
        Ta[task].x = c;
        Ta[task].y = b;
        Ta[task].nr = task;
    }
    Ta[ task+1 ].x = INF;
    Ta[ task+1 ].y = INF;
 
    sort ( El.begin(), El.end() );
  
    sort ( Ta+1, Ta+4*m+1, mysort );
    sort ( Po+1, Po+n+1, mysort );
 
    int ind1=1, ind2=1, act;
 
    for ( ; ind1<=n || ind2<=4*m; ){
        act = min ( Po[ind1].y , Ta[ind2].y );
        // inseram punctele noi in AIB
        while ( (ind1<=n) && ( Po[ind1].y == act ) ){
            add ( bs ( Po[ind1].x ) , 1 );
            ind1++;
        }
        // facem queryurile 
        while ( ( ind2<=4*m ) && ( Ta[ind2].y == act ) ){
            Rez [ Ta[ind2].nr ] = query ( bs ( Ta[ind2].x ) );
            ind2++;
        }
    }
 
    for ( i=1; i<=m; i++ ){
        rez=0;
        rez += Rez[ (i-1)*4+1 ];
        rez += Rez[ (i-1)*4+2 ];
        rez -= Rez[ (i-1)*4+3 ];
        rez -= Rez[ (i-1)*4+4 ];
//        printf("%d\n",rez);
    }
 
    return 0;
}