Cod sursa(job #1153423)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 25 martie 2014 14:21:10
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define N 65000
using namespace std;

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

struct data {
    int x;
    int y;
}v[20005];

vector <int> a[N];

int X1,Y1,X2,Y2,i,j,mid,dr,st,sum,A,b,n,m;


void interclasare (int I, int J, int K){

    a[I].clear();
    int n=a[J].size()-1;
    int m=a[K].size()-1;
    int i=0,j=0;

    while (i<=n && j<=m) {
        if (a[J][i]<a[K][j]){
            a[I].push_back(a[J][i]);
            i++;
        }else{
            a[I].push_back(a[K][j]);
            j++;
        }
    }

    for (;i<=n;i++)
        a[I].push_back(a[J][i]);

    for (;j<=m;j++)
        a[I].push_back(a[K][j]);

}

void update (int nod, int st, int dr){

    if (st==dr) {
        a[nod].push_back(v[i].y);
        return;
    }
    int mid=(st+dr)/2;

    if (i<=mid)
        update (nod*2,st,mid);

    else
        if (i>mid)
            update (nod*2+1,mid+1,dr);

    if (a[2*nod].size () !=0 && a[2*nod+1].size()!=0)
        interclasare (nod,nod*2,nod*2+1);

}

void query (int nod, int st, int dr) {

    if (A<=st && b>=dr) {
        int p=0;
        int u=a[nod].size()-1;
        while (p<=u) {
            mid=(p+u)/2;
            if (a[nod][mid]>=Y1)
                u=mid-1;
            else
                p=mid+1;
        }
        int qs=p;
        p=0;u=a[nod].size()-1;
        while (p<=u) {
            mid=(p+u)/2;
            if (a[nod][mid]>Y2)
                u=mid-1;
            else
                p=mid+1;
        }
        int qd=u;
        sum+=(qd-qs+1);
        return;
    }
    if(st==dr)
    return;
    int mid=(st+dr)/2;
    if (A<=mid)
        query(nod*2,st,mid);
    if (b>mid)
        query(nod*2+1,mid+1,dr);


}
bool cmp (const data &a, const data &b) {
    return a.x<b.x;
}

int main () {

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

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

    for (i=1;i<=n;i++)
        update (1,1,n);

    fin>>m;

    while (m--) {
        fin>>X1>>Y1>>X2>>Y2;
        st=1;dr=n;
        while (st<=dr) {
            mid=(st+dr)/2;
            if (v[mid].x>=X1)
                dr=mid-1;
            else
                st=mid+1;
        }
        A=st;
        st=1;dr=n;
        while (st<=dr) {
            mid=(st+dr)/2;
            if (v[mid].x>X2)
                dr=mid-1;
            else
                st=mid+1;
        }
        b=dr;
        sum=0;
        query(1,1,n);
        fout<<sum<<"\n";
    }


    return 0;
}