Cod sursa(job #1705789)

Utilizator Bodo171Bogdan Pop Bodo171 Data 20 mai 2016 23:28:05
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
int i,n,q,x1,x2,y11,y2,pos,val,f1,f2,j,var1,var2,p,u,mij,rasp;
vector<int> v[48005];
struct punct
{
    int x,y;
}a[16005];
bool comp(punct g,punct h)
{
    if(g.x==h.x) return g.y<h.y;
    return g.x<h.x;
}
void insertx(int nod,int l,int r)
{
    if(l==r)
    {
        v[nod].push_back(a[pos].y);
        return;
    }
    int m=(l+r)/2;
    if(pos<=m) insertx(2*nod,l,m);
    else insertx(2*nod+1,m+1,r);

}
void mergebuild(int nod,int l,int r)
{
    if(l==r) return;
    int m=(l+r)/2;
    mergebuild(2*nod,l,m);
    mergebuild(2*nod+1,m+1,r);
    f1=2*nod;f2=2*nod+1;
    i=0;j=0;
    while(i<v[f1].size()&&j<v[f2].size())
    {
        if(v[f1][i]<v[f2][j]) {v[nod].push_back(v[f1][i]);i++;}
        else {v[nod].push_back(v[f2][j]);j++;}
    }
    for(i;i<v[f1].size();i++) v[nod].push_back(v[f1][i]);
    for(j;j<v[f2].size();j++) v[nod].push_back(v[f2][j]);
}
int binsearch(int a,int val)
{
    p=0;u=v[a].size()-1;
    if(v[a][0]>=val) return 0;
    if(v[a][u]<=val) return u;
    while(u-p>1)
    {
        mij=(p+u)/2;
        if(v[a][mij]<val) p=mij;
        else u=mij;
    }
    return u;
}
void query(int nod,int l,int r)
{
    if(x1<=a[l].x&&a[r].x<=x2)
    {
        var1=binsearch(nod,y11);
        var2=binsearch(nod,y2+1);
        if(v[nod][var1]<y11) var1++;
        while(v[nod][var2]>y2&&var2>=0) var2--;
        if(var1<=var2)rasp+=var2-var1+1;
        return;
    }
    int m=(l+r)/2;
    if(x1<=a[m].x)query(2*nod,l,m);
    if(a[m].x<x2) query(2*nod+1,m+1,r);
}
int main()
{
    ifstream f("zoo.in");
    ofstream g("zoo.out");
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,comp);
    for(i=1;i<=n;i++)
    {
        pos=i;
        val=a[i].x;
        insertx(1,1,n);
    }
    mergebuild(1,1,n);
    f>>q;
    for(i=1;i<=q;i++)
    {
        f>>x1>>y11>>x2>>y2;
        rasp=0;
        if(x2<a[1].x||x1>a[n].x) rasp=0;
           else query(1,1,n);
        g<<rasp<<'\n';
    }
    return 0;
}