Cod sursa(job #170431)

Utilizator cos_minBondane Cosmin cos_min Data 2 aprilie 2008 19:11:45
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 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 Maxim(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;
    
    Update(1,1,1,N);
    
    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 ) dr = mij-1;
          else                pos = Maxim(pos,mij), st = mij+1;
                       
    }
    
    return pos;
}

void Update(int nod, int niv, int left, int right)
{
     if ( left == right )
     {
          Arb[niv][left] = Y[left];
          return;
     }
     
     int div = (left+right)>>1;
     Update(ind,niv+1,left,div);
     Update(ind+1,niv+1,div+1,right);
     
     int x = left, y = div+1, k = left;
     for ( ; k <= right; k++ )
     {
         if ( y > right || ( x <= div && Arb[niv+1][x] <= Arb[niv+1][y] ) ) Arb[niv][k] = Arb[niv+1][x], x++;
         else                                                               Arb[niv][k] = Arb[niv+1][y], 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);
}