Cod sursa(job #290166)

Utilizator flamecataCiobanu Alexandru-Catalin flamecata Data 27 martie 2009 16:28:18
Problema Zoo Scor 100
Compilator cpp Status done
Runda aa Marime 2.99 kb
#include<cstdio>   
#include<algorithm>   
#include<vector>   
using namespace std;   
#define MAX_N 16002   
#define pb push_back   
#define x first   
#define y second   
vector <int> H[4*MAX_N+3];   
pair <int,int> P[MAX_N];   
int N,M;   
int x1,x2,y2,y1;   
int sol;   
void read()   
 {   
      freopen("zoo.in","r",stdin);   
      freopen("zoo.out","w",stdout);   
      scanf("%d",&N);   
      int i,X,Y;   
      for(i=1;i<=N;++i)   
        {    
            scanf("%d %d",&X,&Y);   
            P[i].first = X; P[i].second = Y;   
        }   
 }   
void merge(int n)   
{   
    int fs=2*n, fd=2*n+1;   
    // H[n] = H[fs] + H[fd] ;   
    int i=0, j=0;   
    int l1 = H[fs].size();   
    int l2 = H[fd].size();   
    while(i<l1 && j<l2)   
    {   
        if(H[fs][i] < H[fd][j]){ H[n].pb(H[fs][i]); ++i; }   
        else if(H[fs][i] > H[fd][j]) { H[n].pb(H[fd][j]); ++j; }   
        else { H[n].pb(H[fd][j]); H[n].pb(H[fd][j]); ++i; ++j;}   
    }   
    while(i<l1) { H[n].pb(H[fs][i]); ++i; }   
    while(j<l2) { H[n].pb(H[fd][j]); ++j; }   
}   
  
void build(int n, int l, int r)   
 {   
     if(l==r)   
     {   
         H[n].pb(P[r].y);   
         //print(n);   
         return;   
     }   
     int m=(l+r)/2, fs=2*n, fd=2*n+1;   
     build(fs, l, m);   
     build(fd,m+1,r);   
        
     merge(n);   
     //print(n);   
 }   
int nr_puncte(int n, int y1, int y2)   
 {   
     int m,i,j;   
     int s1=0, s2=0;   
     if(H[n][0] > y2) return 0;   
     if(H[n][H[n].size()-1] < y1) return 0;   
     i=0; j=H[n].size()-1;   
     while(i<=j)   
     {   
         m=(i+j)/2;   
         if(H[n][m] < y1 ) i=m+1;   
         else {   
             if(m==0) break;   
             else if(H[n][m-1] < y1) break;   
             else j=m-1;   
         }   
     }   
     if(i>j) return 0;   
     s1 = m;   
     i=0; j=H[n].size()-1;   
     int l = H[n].size();   
     while(i<=j)   
     {   
         m=(i+j)/2;   
         if(H[n][m] > y2) j=m-1;   
         else    
             {   
                 if(m == l-1) break;   
                 if(H[n][m+1] > y2) break;   
                 i=m+1;   
             }   
     }   
     s2=m;   
     if(i>j) return 0;   
     return s2-s1+1;   
}   
void query(int n, int l, int r) // vad cate pcte exista in dreptunghiul (x1,y1,x2,y2)   
 {   
     if(x1<=P[l].x && P[r].x<=x2)   
     {   
         sol += nr_puncte(n, y1, y2);   
         return;   
     }   
     else if(l!=r){   
     int m=(l+r)/2, fs=2*n, fd=2*n+1;   
     if(x1<=P[m].x) query(fs,l,m);   
     if(x2>=P[m+1].x) query(fd,m+1,r);}   
 }   
void solve()   
{   
    scanf("%d",&M);   
    while(M--)   
    {   
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);   
        sol=0;   
        query(1,1,N);   
        printf("%d\n",sol);   
    }   
 }   
int main()   
{   
    read();   
    sort(P+1,P+N+1);   
    build(1,1,N);   
    solve();   
    return 0;   
}