Cod sursa(job #607017)

Utilizator crushackPopescu Silviu crushack Data 10 august 2011 16:44:32
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <assert.h>
#define NMax 16010
#define MMax 100010
#define CMax (2*NMax + 4*MMax)
using namespace std;

const char IN[]="zoo.in",OUT[]="zoo.out";

struct point{
    int x,y;
} p[NMax];

struct query{
    int x,y,x2,y2;
} q[MMax];


int N,M,L,k,STEP;
int v[CMax];
vector<int> vec[CMax];
vector<int> arb[CMax<<2];

char s[1024],*r;

 int lower_bound(int x)
{
    int step,i;
    for (step=1;step<L;step<<=1);
    for (i=L;step;step>>=1)
        if (i-step>=0 && v[i-step]>=x)
            i-=step;
    return i;
}

int upper_bound(int x)
{
    int step,i;
    for (step=1;step<L;step<<=1);
    for (i=0;step;step>>=1)
        if (i+step>=0 && v[i+step]<=x)
            i+=step;
    return i;
}

void make(int poz,int st,int dr)
{
    if (st==dr){
        arb[poz]=vec[st];
        sort(arb[poz].begin(),arb[poz].end());
        return;
    }
    int m=(st+dr)>>1;
    make(2*poz,st,m);
    make(2*poz+1,m+1,dr);

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

int query(int poz,int st,int dr,int x,int y,int x2,int y2)
{
    if ( x<=st && dr<= x2 )
        return upper_bound(arb[poz].begin(),arb[poz].end(),y2)-lower_bound(arb[poz].begin(),arb[poz].end(),y);
    int m=(st+dr)>>1,r1=0,r2=0;

    if ( x <= m ) r1=query(2*poz,st,m,x,y,x2,y2);
    if ( x2 > m ) r2=query(2*poz+1,m+1,dr,x,y,x2,y2);
    return r1+r2;
}

inline int next(){
    int ret=0;
    while (*r && (*r<'0' || *r>'9')) ++r;
    while ( *r>='0' && *r<='9' )
        ret= 10*ret + *r -'0',
        ++r;
    return ret;
}

int main()
{
    int i;
    freopen(IN,"r",stdin);
    scanf("%d",&N);
    for (i=0;i<N;++i)
        fgets( s , 1024 , stdin ),r=s,
        //scanf("%d%d",&p[i].x,&p[i].y),
        p[i].x=next(),p[i].y=next(),
        v[L++]=p[i].x,
        v[L++]=p[i].y;
    scanf("%d",&M);
    for (i=0;i<M;++i)
        fgets( s , 1024 , stdin ),r=s,
        //scanf("%d%d%d%d",&q[i].x,&q[i].y,&q[i].x2,&q[i].y2),
        q[i].x=next(),q[i].y=next(),q[i].x2=next(),q[i].y2=next(),
        v[L++]=q[i].x,v[L++]=q[i].y,v[L++]=q[i].x2,v[L++]=q[i].y2;
    fclose(stdin);

    sort(v,v+L);
    L=unique(v,v+L)-v;

    for (STEP=1;STEP<L;STEP<<=1);

    for (i=0;i<N;++i)
        p[i].x=lower_bound(p[i].x),
        p[i].y=lower_bound(p[i].y),
        vec[p[i].x].push_back(p[i].y);
    for (i=0;i<M;++i)
    {
        q[i].x=lower_bound(q[i].x);
        q[i].x2=lower_bound(q[i].x2);
        q[i].y=lower_bound(q[i].y);
        q[i].y2=lower_bound(q[i].y2);
    }

    make(1,0,L-1);

    freopen(OUT,"w",stdout);
    for (i=0;i<M;++i)
        printf("%d\n",query(1,0,L-1,q[i].x,q[i].y,q[i].x2,q[i].y2));
    fclose(stdout);
    return 0;
}