Cod sursa(job #1296794)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 21 decembrie 2014 15:14:11
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define DIM 16011
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int n,m;
pair<int,int> v[DIM];

vector<int> A[4*DIM+1];

void build(int nod,int p,int u){
    if(p==u){
        A[nod].push_back(p);
        return;
    }
    int mid=p+(u-p)/2,i,j;
    build(2*nod,p,mid);
    build(2*nod+1,mid+1,u);

    i=j=0;
    while(i<A[2*nod].size() && j<A[2*nod+1].size()){
        if(v[A[2*nod][i]].second<=v[A[2*nod+1][j]].second)
            A[nod].push_back(A[2*nod][i]),i++;
        else
            A[nod].push_back(A[2*nod+1][j]),j++;
    }
    for(;i<A[2*nod].size();i++)
        A[nod].push_back(A[2*nod][i]);
    for(;j<A[2*nod+1].size();j++)
        A[nod].push_back(A[2*nod+1][j]);
  /*  g<<nod<<" ";
    for(i=0;i<A[nod].size();i++) g<<A[nod][i];
    g<<"\n";*/
}

int query1(int x){
    int p,u,mid;
    p=1,u=n;
    while(p<=u){
        mid=p+(u-p)/2;
        if(v[mid].first>=x)
            u=mid-1;
        else
            p=mid+1;
    }
    return p;
}

int query2(int x){
    int p,u,mid;
    p=1,u=n;
    while(p<=u){
        mid=p+(u-p)/2;
        if(v[mid].first<=x)
            p=mid+1;
        else
            u=mid-1;
    }
    return u;
}

int query3(int nod,int y){
    int p,u,mid;
    p=0,u=A[nod].size()-1;
    while(p<=u && u>=0 && p<=A[nod].size()){
        mid=p+(u-p)/2;
        if(v[A[nod][mid]].second>=y)
            u=mid-1;
        else
            p=mid+1;
    }
    return p;
}

int query4(int nod,int y){
    int p,u,mid;
    p=0,u=A[nod].size()-1;
    while(p<=u && u>=0 && p<=A[nod].size()){
        mid=p+(u-p)/2;
        if(v[A[nod][mid]].second<=y)
            p=mid+1;
        else
            u=mid-1;
    }
    return u;
}

int query(int nod,int p,int u,int a,int b,int c,int d){
    if(a<=p && u<=b){
        c=query3(nod,c);
        d=query4(nod,d);
        return (d-c+1);
    }
    int mid=p+(u-p)/2,sum=0;
    if(a<=mid)
        sum+=query(2*nod,p,mid,a,b,c,d);
    if(b>mid)
        sum+=query(2*nod+1,mid+1,u,a,b,c,d);
    return sum;
}

int main(void){
    register int i,j,x1,y1,x2,y2;

    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].first>>v[i].second;
    sort(v+1,v+n+1);
    build(1,1,n);

    f>>m;
    for(i=1;i<=m;i++){
        f>>x1>>y1>>x2>>y2;
        x1=query1(x1);
        x2=query2(x2);
        g<<query(1,1,n,x1,x2,y1,y2)<<"\n";
    }

    f.close();
    g.close();
    return 0;
}