Cod sursa(job #606989)

Utilizator crushackPopescu Silviu crushack Data 10 august 2011 16:07:24
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <assert.h>
#define NMax 16010
#define MMax 100010
#define CMax (2*NMax + 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;
int v[CMax];
vector<int> vec[CMax];
vector<int> arb[CMax<<5];

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());
        //for (int i=0;i<(int)arb[poz].size();++i) printf("%d ",arb[poz][i]); printf("\n");
        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());

    //for (int i=0;i<(int)arb[poz].size();++i) printf("%d ",arb[poz][i]); printf("\n");
}

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;
}

int main()
{
    int i;
    freopen(IN,"r",stdin);
    scanf("%d",&N);
    for (i=0;i<N;++i)
        scanf("%d%d",&p[i].x,&p[i].y),
        v[L++]=p[i].x,
        v[L++]=p[i].y;
    scanf("%d",&M);
    for (i=0;i<M;++i)
        scanf("%d%d%d%d",&q[i].x,&q[i].y,&q[i].x2,&q[i].y2),
        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 (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);

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