Mai intai trebuie sa te autentifici.
Cod sursa(job #1226619)
Utilizator | Data | 6 septembrie 2014 15:25:23 | |
---|---|---|---|
Problema | Zoo | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.68 kb |
#include <cstdio>
#include <vector>
#include <algorithm>
#define Nmax 16005
using namespace std;
int N;
vector <int> a,aint[3*Nmax];
struct pc
{
int x,y;
bool operator < (const pc A) const
{
return x<A.x;
}
};
pc v[Nmax];
inline void Build(int nod, int st, int dr)
{
if(st==dr)
{
aint[nod].push_back(v[st].y);
return;
}
int mij=((st+dr)>>1);
Build(2*nod,st,mij); Build(2*nod+1,mij+1,dr);
aint[nod].resize(aint[2*nod].size()+aint[2*nod+1].size());
merge(aint[2*nod].begin(),aint[2*nod].end(),aint[2*nod+1].begin(),aint[2*nod+1].end(),aint[nod].begin());
}
inline int Query(int nod, int st, int dr, int p1, int p2, int x, int y)
{
if(st==p1 && p2==dr)
return upper_bound(aint[nod].begin(),aint[nod].end(),y)-lower_bound(aint[nod].begin(),aint[nod].end(),x);
int mij=((st+dr)>>1);
if(p2<=mij)
return Query(2*nod,st,mij,p1,p2,x,y);
if(p1>mij)
return Query(2*nod+1,mij+1,dr,p1,p2,x,y);
return Query(2*nod,st,mij,p1,mij,x,y)+Query(2*nod+1,mij+1,dr,mij+1,p2,x,y);
}
int main()
{
int i,M,x1,x2,y1,y2,ind1,ind2;
freopen ("zoo.in","r",stdin);
freopen ("zoo.out","w",stdout);
scanf("%d", &N);
for(i=1;i<=N;++i)
scanf("%d%d", &v[i].x,&v[i].y);
sort(v+1,v+N+1);
for(i=1;i<=N;++i)
a.push_back(v[i].x);
Build(1,1,N);
scanf("%d", &M);
while(M--)
{
scanf("%d%d%d%d", &x1,&y1,&x2,&y2);
ind1=lower_bound(a.begin(),a.end(),x1)-a.begin();
ind2=upper_bound(a.begin(),a.end(),x2)-a.begin()-1;
printf("%d\n", Query(1,1,N,ind1+1,ind2+1,y1,y2));
}
return 0;
}