Cod sursa(job #847868)

Utilizator cristicecCristian Uricec cristicec Data 4 ianuarie 2013 16:31:33
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
 
const int N=16001;
int X[N],Y[N],n,pX,pY;
struct punct{int x,y;} a[N];
vector <int> v[5*N];
 
ifstream in("zoo.in");
ofstream out("zoo.out");
 
bool comp(const punct &a,const punct &b)
{
    return a.y<b.y;
}
 
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-1);
}
 
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()
{
    in>>n;
    int x,y,z,t,i,m;
    for (i=1;i<=n;i++)
    {
        in>>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));
    in>>m;
    while (m--)
    {
        in>>x>>y>>z>>t;
        pX=bs(Y,y);pY=bs(Y,t);
        out<<query(1,1,X[0],bs(X,x),bs(X,z))<<"\n";
    }
    return 0;
}