Cod sursa(job #2071175)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 20 noiembrie 2017 14:12:24
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<fstream>
#include<algorithm>
#include<vector>
#define x first
#define y second

using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int n, m, i1, i2, j1, j2, nr, i;
vector<int> a[64002];
pair<int, int> v[16002];

void build(int nod, int st, int dr){
    if(st==dr)
        a[nod].push_back(st);
    else
    {
        int mid=(st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        int i=0, j=0;
        int s=nod*2, d=nod*2+1;
        while(i<a[s].size()&&j<a[d].size())
        {
            if(v[a[s][i]].y<v[a[d][j]].y)
            {
                a[nod].push_back(a[s][i]);
                i++;
            }
            else
            {
                a[nod].push_back(a[d][j]);
                j++;
            }
        }
        for(;i<a[s].size();i++)
            a[nod].push_back(a[s][i]);

        for(;j<a[d].size();j++)
            a[nod].push_back(a[d][j]);
    }
}

void query(int nod, int st, int dr)
{
    if(i1<=v[st].x&&v[dr].x<=i2)
    {
        int p=0, u=a[nod].size()-1, mid, aux;
        while(p<=u)
        {
            mid=(p+u)/2;
            if(v[a[nod][mid]].y>=j1)
                u=mid-1;
            else
                p=mid+1;
        }
        aux=p;
        p=0;
        u=a[nod].size()-1;
        while(p<=u)
        {
            mid=(p + u)/2;
            if(v[a[nod][mid]].y>j2)
                u=mid-1;
            else
                p=mid+1;
        }
        nr+=(u-aux+1);
    }
    else
    {
        int mid=(st+dr)/2;
        if(i1<=v[mid].x)
            query(nod*2, st, mid);
        if(i2>=v[mid+1].x)
            query(nod*2+1, mid+1, dr);
    }
}

int main(){
    fin>>n;
    for(i=1;i<=n;i++)
         fin>>v[i].x>>v[i].y;
    sort(v+1, v+n+1);
    build(1, 1, n);
    fin>>m;
    for(i=1;i<=m;i++)
    {
        fin>>i1>>j1>>i2>>j2;
        nr=0;
        if(v[1].x>i2||v[n].x<i1)
        {
            fout<<0<<"\n";
            continue;
        }
        query(1, 1, n);
        fout<<nr<<"\n";
    }
    return 0;
}