Cod sursa(job #169775)

Utilizator ninjaNo name ninja Data 1 aprilie 2008 22:31:02
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <stdio.h>
#include <fstream>
#include <utility>
#include <set>
using namespace std;

#define in "zoo.in"
#define out "zoo.out"
#define dim 16001
#define Minim(a,b) a < b ? a : b
#define ind (nod<<1)

int N, M, A, B, Total;
int x1, x2, y1, y2;
int X[dim], Y[dim];
int Arb[16][3*dim];

multiset< pair<int,int> > H;
multiset< pair<int,int> >::iterator it;

void Update(int,int,int,int);
void Query(int,int,int,int);
int Search(int[],int,int,int);

int main()
{
    int x, y;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d", &N);
    for ( int i = 1; i <= N; i++ )
    {
        scanf("%d%d", &x, &y);
        H.insert( make_pair(x,y) );
    }
    
    int s = 1;
    for ( it = H.begin(); it != H.end(); it++, s++ )
    {
        X[s] = it->first, Y[s] = it->second;
        A = s, B = Y[s];
        Update(1,1,1,N);
    }
    
    int st, dr, mij;
    
    scanf("%d", &M);
    for ( ; M; M-- )
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2 );
        
        if ( x1 > X[N] || x2 < X[1] )
        {
             printf("0\n");
             continue;
        }
        
        Total = 0;
        A = Search(X,1,N,x1-1)+1;
        B = Search(X,1,N,x2);
        Query(1,1,1,N);
        
        printf("%d\n", Total);
    }
}

int Search(int H[], int st, int dr, int val)
{
    int mij, pos=st-1;
    
    while ( st <= dr )
    {
          mij = (st+dr)>>1;
          if ( H[mij] <= val ) pos = mij, st = mij+1;
          else                dr = mij-1;
    }
    
    return pos;
}

void Update(int nod, int niv, int left, int right)
{
     if ( left == right )
     {
          Arb[niv][left] = B;
          return;
     }
     
     int div = (left+right)>>1;
     if ( A <= div ) Update(ind,niv+1,left,div);
     else            Update(ind+1,niv+1,div+1,right);
     
     int x = left, y = div+1, k = left;
     for ( ; k <= right; x++, y++, k++ )
     {
         if ( x > div )        Arb[niv][k] = Arb[niv+1][y];
         else if ( y > right ) Arb[niv][k] = Arb[niv+1][x];
         else                  Arb[niv][k] = Minim(Arb[niv+1][x],Arb[niv+1][y]);
     }
}

void Query(int nod, int niv, int left, int right)
{
     if ( A <= left && right <= B )
     {
          Total += Search(Arb[niv],left,right,y2)-Search(Arb[niv],left,right,y1-1);
          return;
     }
     
     int div = (left+right)>>1;
     if ( A <= div ) Query(ind,niv+1,left,div);
     if ( div < B )  Query(ind+1,niv+1,div+1,right);
}