Cod sursa(job #981680)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 7 august 2013 18:27:27
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define maxn 16005
#define maxait 1<<17
using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

vector <int> ait[maxait];
struct point{int x,y;} p[maxn];
int n,m,sol;
int dx1,dx2,dy1,dy2;
int px[maxn];

void read()
{
    fin>>n;
    for(int i=1;i<=n;i++) fin>>p[i].x>>p[i].y,px[i]=p[i].x;
}

int cmp(point a,point b){ return a.x<b.x; }

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);
    sort(px+1,px+n+1);
    build(1,1,n);
}

int count(int k)
{
    if(dy1>ait[k][ait[k].size()-1] || dy2<ait[k][0])
     return 0;

    return ub(ait[k].begin(),ait[k].end(),dy2)-lb(ait[k].begin(),ait[k].end(),dy1);
}

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 l,r;
    fin>>m;
    for(int k=1;k<=m;k++)
    {
        fin>>dx1>>dy1>>dx2>>dy2;
        if(dx1>p[n].x || dx2<p[1].x)
         {fout<<"0"<<'\n'; continue;}

        l=lb(px+1,px+n+1,dx1)-px;
        r=ub(px+1,px+n+1,dx2)-px-1;
        sol=0; query(1,1,n,l,r);
        fout<<sol<<'\n';
    }
}

int main()
{
    read();
    tree();
    solve();

    fin.close();
    fout.close();
    return 0;
}