Cod sursa(job #981384)

Utilizator andrettiAndretti Naiden andretti Data 6 august 2013 22:49:56
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define maxn 16005
#define maxait 1<<17
#define maxstep 1<<15
using namespace std;

vector <int> ait[maxait];
struct point{int x,y;} p[maxn],pl,pr;
int n,m,sol;

void read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
}

int cmp(point a,point b){ if(a.x==b.x) return a.y<b.y; return a.x<b.x; }
int cmpy(int a,int b) { return a<b; }

void build(int k,int left,int right)
{
    if(left==right) {ait[k].pb(p[left].y); return;}
    int mid=(left+right)>>1;
    build(2*k,left,mid);
    build(2*k+1,mid+1,right);

    ait[k].resize(ait[2*k].size()+ait[2*k+1].size());
    merge(ait[2*k].begin(),ait[2*k].end(),ait[2*k+1].begin(),ait[2*k+1].end(),ait[k].begin());
}

void tree()
{
    sort(p+1,p+n+1,cmp);
    build(1,1,n);
}

int count(int k)
{
    int step,i,l,r;

    if(pl.y>ait[k][ait[k].size()-1] || pr.y<ait[k][0])
     return 0;

    step=maxstep;
    for(i=-1;step;step>>=1)
     if(i+step<=ait[k].size()-1)
     {
         if(ait[k][i+step]>=pl.y) l=step+i;
         else i+=step;
     }
    step=maxstep;
    for(i=-1;step;step>>=1)
         if(i+step<=ait[k].size()-1 && ait[k][i+step]<=pr.y)
          i+=step;
    r=i;
    return r-l+1;
}

void query(int k,int left,int right,int x,int y)
{
    if( x<=left && right<=y ) { sol+=count(k); return;}
    int mid=(left+right)>>1;
    if(x<=mid) query(2*k,left,mid,x,y);
    if(y>mid) query(2*k+1,mid+1,right,x,y);
}

void solve()
{
    int step,i,l,r;
    scanf("%d",&m);
    for(int k=1;k<=m;k++)
    {
        scanf("%d%d%d%d",&pl.x,&pl.y,&pr.x,&pr.y);
        if(pl.x>p[n].x || pr.x<p[1].x)
         {printf("0\n"); continue;}

        step=maxstep;
        for(i=0;step;step>>=1)
         if(i+step<=n)
         {
             if(p[i+step].x>=pl.x) l=i+step;
             else i+=step;
         }
        step=maxstep;
        for(i=0;step;step>>=1)
         if(i+step<=n && p[i+step].x<=pr.x)
          i+=step;
        r=i;
        sol=0; query(1,1,n,l,r);
        printf("%d\n",sol);
    }
}

int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);

    read();
    tree();
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}