Cod sursa(job #1093075)

Utilizator teoionescuIonescu Teodor teoionescu Data 27 ianuarie 2014 18:44:31
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<queue>
#define abs(x) ((x>0)?(x):(-(x)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ll long long
using namespace std;
ifstream in("zoo.in");
ofstream out("zoo.out");
const int Nmax = 16005;
int N,M;
struct Point{
    int x,y;
} v[Nmax],a,b;
int VX[Nmax];
bool cmp(Point _a,Point _b){
    return _a.x < _b.x;
}
vector<int> A[18*Nmax];
int Max;
void Update(int i,int st,int dr,int& w){
    if(i>Max) Max=i;
    A[i].push_back(v[w].y);
    if(st<dr){
        int mij=(st+dr)/2;
        if(w<=mij) Update(2*i,st,mij,w);
        else Update(2*i+1,mij+1,dr,w);
    }
}
int BinS(vector<int> X){
    int i=-1,j=-1,pas;
    pas=1<<20;
    while(pas){
        if(i+pas<X.size() && X[i+pas]<a.y) i+=pas;
        pas>>=1;
    }
    pas=1<<20;
    while(pas){
        if(j+pas<X.size() && X[j+pas]<=b.y) j+=pas;
        pas>>=1;
    }
    return j-i;
}
int Query(int i,int st,int dr,int aa,int bb){
    if(!A[i].size()) return 0;
    if(aa<=VX[st] && VX[dr]<=bb){
        return BinS(A[i]);
    }
    else{
        int mij=(st+dr)/2;
        if(bb<=VX[mij]) return Query(2*i,st,mij,aa,bb);
        else if(aa>VX[mij]) return Query(2*i+1,mij+1,dr,aa,bb);
        else return ( Query(2*i,st,mij,aa,VX[mij]) + Query(2*i+1,mij+1,dr,VX[mij+1],bb) );
    }
}
int main(){
    in>>N;
    for(int i=1;i<=N;i++) in>>v[i].x>>v[i].y;
    sort(v+1,v+N+1,cmp);
    for(int i=1;i<=N;i++) VX[i]=v[i].x;
    sort(VX+1,VX+N+1);
    for(int i=1;i<=N;i++) Update(1,1,N,i);
    for(int i=1;i<=Max;i++){
        sort(A[i].begin(),A[i].end());
    }
    in>>M;
    for(int i=1;i<=M;i++){
        in>>a.x>>a.y;
        in>>b.x>>b.y;
        out<<Query(1,1,N,a.x,b.x)<<'\n';
    }
    return 0;
}