Cod sursa(job #1153987)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 25 martie 2014 21:35:37
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

vector< int > A[65005];

int n,m,i,p,u,mid,sol,x,xx,y,yy,a,b,stanga,dreapta;

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

void query(int nod,int st,int dr);
void update(int nod,int st,int dr);
void intercl(int nod);

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

int main() {
    ifstream f("zoo.in");
    ofstream g("zoo.out");
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++)
        update(1,1,n);
    f>>m;
    while(m--) {
        f>>x>>y>>xx>>yy;
        p=1;u=n;
        while(p<=u) {
            mid=p+(u-p)/2;
            if(v[mid].x>=x)
                u=mid-1;
            else
                p=mid+1;
        }
        a=p;
        p=1;u=n;
        while(p<=u) {
            mid=p+(u-p)/2;
            if(v[mid].x>xx)
                u=mid-1;
            else
                p=mid+1;
        }
        b=u;
        sol=0;
        query(1,1,n);
        g<<sol<<"\n";
    }
    return 0;
}
void intercl(int nod) {
    A[nod].clear();
    int m=A[nod*2].size()-1;
    int n=A[nod*2+1].size()-1;
    int i=0,j=0;
    while(i<=m && j<=n) {
        if(A[nod*2][i]<A[nod*2+1][j]) {
            A[nod].push_back(A[nod*2][i]);
            i++;
        }
        else {
            A[nod].push_back(A[nod*2+1][j]);
            j++;
        }
    }
    for(;i<=m;i++)
        A[nod].push_back(A[nod*2][i]);
    for(;j<=n;j++)
        A[nod].push_back(A[nod*2+1][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
        update(nod*2+1,mid+1,dr);
    if(!A[2*nod].empty() && !A[2*nod+1].empty())
        intercl(nod);
}
void query(int nod, int st, int dr) {
    if(a<=st && b>=dr) {
        int p=0,u=A[nod].size()-1;
        int mid;
        while(p<=u) {
            mid=(p+u)/2;
            if(A[nod][mid]>=y)
                u=mid-1;
            else
                p=mid+1;
        }
        stanga=p;
        p=0;u=A[nod].size()-1;
        while(p<=u) {
            mid=(p+u)/2;
            if(A[nod][mid]>yy)
                u=mid-1;
            else
                p=mid+1;
        }
        dreapta=u;
        sol+=dreapta-stanga+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);
}