Cod sursa(job #598274)

Utilizator mihai995mihai995 mihai995 Data 25 iunie 2011 01:03:46
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N=16001;
int X[N],Y[N],n,pX,pY,D=-1;
char PRINT[100*N];
struct punct{int x,y;} a[N];
vector <int> v[5*N];

bool comp(const punct &a,const punct &b)
{
    return a.y<b.y;
}

void add(int x)
{
    if (x<10)
    {
        PRINT[++D]=x+'0';
        return;
    }
    add(x/10);
    PRINT[++D]=x%10+'0';
}

void comprim(int v[])
{
    int i,j;
    sort(v+1,v+n+1);
    for (i=j=1;j<=n;i++)
    {
        v[i]=v[j];
        while (j<=n && v[i]==v[j])
            j++;
    }
    v[0]=i-1;
}

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

int bs(vector<int> &v,int x)
{
    int i,step=1<<13;
    for (i=-1;step;step>>=1)
        if (i+step<v.size() && v[i+step]<=x)
            i+=step;
    return i;
}

int proc(vector<int> &v)
{
    return bs(v,pY)-bs(v,pX);
}

void update(int x,int val)
{
    int poz=1,st=1,dr=X[0],m;
    while (st!=dr)
    {
        v[poz].push_back(val);
        poz<<=1;
        m=(st+dr)>>1;
        if (x<=m)
            dr=m;
        else
        {
            st=m+1;
            poz++;
        }
    }
    v[poz].push_back(val);
}

int query(int poz,int st,int dr,int x,int y)
{
    if (5*N<=poz || y<st || dr<x || v[poz].empty())
        return 0;
    if (x<=st && dr<=y)
        return proc(v[poz]);
    int m=(st+dr)>>1,S=poz<<1,D=S+1;
    return query(S,st,m,x,y)+query(D,m+1,dr,x,y);
}

int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d",&n);
    int x,y,z,t,i,m;
    for (i=1;i<=n;i++)
    {
        scanf("%d %d",&a[i].x,&a[i].y);
        X[i]=a[i].x;
        Y[i]=a[i].y;
    }
    sort(a+1,a+n+1,comp);
    comprim(X);comprim(Y);
    for (i=1;i<=n;i++)
        update(bs(X,a[i].x),bs(Y,a[i].y));
    scanf("%d",&m);
    while (m--)
    {
        scanf("%d%d%d%d",&x,&y,&z,&t);
        pX=bs(Y,y-1);pY=bs(Y,t);
        add(query(1,1,X[0],bs(X,x-1)+1,bs(X,z)));
        PRINT[++D]='\n';
    }
    printf(PRINT);
    return 0;
}