Cod sursa(job #1152889)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 25 martie 2014 08:19:27
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

struct point
{
    int x,y;
}v[16001];

vector <int> V[16001*4];
int n,m,ans,l,r,x1,x2,yy1,y2;

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

void create_arb (int node, int left, int right)
{
    if (left == right)
    {
        V[node].push_back (v[left].y);
        return;
    }

    int mid = (left + right)/2;

    create_arb (node<<1,left,mid);
    create_arb ((node<<1)+1,mid+1,right);

    V[node].resize (right-left+1);
    merge (V[node<<1].begin(),V[node<<1].end(),V[(node<<1)+1].begin(),V[(node<<1)+1].end(),V[node].begin());
}

void query (int node, int left, int right)
{
    if (l <= left && right <= r)
    {
        vector<int>::iterator lo = lower_bound (V[node].begin(),V[node].end(),yy1);
        vector<int>::iterator hi = upper_bound (V[node].begin(),V[node].end(),y2);
        ans += hi - lo;
        return;
    }

    int mid = (left + right)/2;

    if (l <= mid)
    query (node<<1,left,mid);
    if (r > mid)
    query ((node<<1)+1,mid+1,right);
}

int main()
{
    fin>>n;

    for (int i=1; i<=n; ++i)
    {
        fin>>v[i].x>>v[i].y;
    }

    sort (v+1,v+n+1,cmp);

    create_arb(1,1,n);

    fin>>m;

    for (int i=1; i<=m; ++i)
    {
        fin>>x1>>yy1>>x2>>y2;

        int lo = 0, hi = n+1;

        while (hi - lo > 1)
        {
            int mid = (lo + hi)/2;
            if (x1 <= v[mid].x)
               hi = mid;
            else lo = mid;
        }

        l = hi;

        lo = 0, hi = n+1;

        while (hi - lo > 1)
        {
            int mid = (lo + hi)/2;
            if (x2 >= v[mid].x)
               lo = mid;
            else hi = mid;
        }

        r = lo;

        ans = 0;
        query(1,1,n);

        fout<<ans<<"\n";
    }
}