Pagini recente » Diferente pentru utilizator/stargold2 intre reviziile 275 si 95 | Istoria paginii utilizator/foxblood001 | Diferente pentru utilizator/stargold2 intre reviziile 120 si 121 | Pitici2 | Cod sursa (job #3162743)
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("zoo.in");
ofstream cout("zoo.out");
struct coord_dreptunghi
{
int x1,y1,x2,y2;
}d[100002];
pair<int,int>coord[16002];
vector<int>aint[5*100001];
int p[5*100000+5],nr,n,m,sol;
int cb(int a)
{
int st=0;
int dr=nr-1;
while(st<=dr)
{
int mid=(st+dr)/2;
if(p[mid]==a)
return mid;
else if(p[mid]>a)
dr=mid-1;
else
st=mid+1;
}
}
int cb_primul(int a,int nod)
{
int st=0;
int dr=aint[nod].size()-1;
while(st<=dr)
{
int mid=(st+dr)/2;
if(aint[nod][mid]>=a)
dr=mid-1;
else
st=mid+1;
}
return st;
}
int cb_ultim(int a,int nod)
{
int st=0;
int dr=aint[nod].size()-1;
while(st<=dr)
{
int mid=(st+dr)/2;
if(aint[nod][mid]<=a)
st=mid+1;
else
dr=mid-1;
}
return dr;
}
void interclaseaza(int nod)
{
int i=0,j=0;
int l1=aint[2*nod].size()-1;
int l2=aint[2*nod+1].size()-1;
while(i<=l1&&j<=l2)
{
if(aint[2*nod][i]<=aint[2*nod+1][j])
aint[nod].push_back(aint[2*nod][i++]);
else
aint[nod].push_back(aint[2*nod+1][j++]);
}
for(;i<=l1;i++)
aint[nod].push_back(aint[2*nod][i]);
for(;j<=l2;j++)
aint[nod].push_back(aint[2*nod+1][j]);
}
void build(int nod,int st,int dr)
{
if(st==dr)
{
aint[nod].push_back(coord[st].second);
}
else
if(st<dr)
{
int mid=(st+dr)/2;
build(2*nod,st,mid);
build(2*nod+1,mid+1,dr);
interclaseaza(nod);
}
}
void query(int nod,int st,int dr,int nr_drept)
{
if(d[nr_drept].x1<=coord[st].first&&coord[dr].first<=d[nr_drept].x2)
sol+=cb_ultim(d[nr_drept].y2,nod)-cb_primul(d[nr_drept].y1,nod)+1;
else
{
if(st==dr)
return;
int mid=(st+dr)/2;
if(d[nr_drept].x1<=coord[mid].first)
query(2*nod,st,mid,nr_drept);
if(d[nr_drept].x2>=coord[mid+1].first)
query(2*nod+1,mid+1,dr,nr_drept);
}
}
int main()
{
cin>>n;
///normalizare
for(int i=1; i<=n; i++)
{
cin>>coord[i].first>>coord[i].second;
p[nr++]=coord[i].first;
p[nr++]=coord[i].second;
}
cin>>m;
for(int i=1; i<=m; i++)
{
cin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2;
p[nr++]=d[i].x1;
p[nr++]=d[i].y1;
p[nr++]=d[i].x2;
p[nr++]=d[i].y2;
}
sort(p,p+nr);
int aux=0;
for(int i=1; i<nr; i++)
if(p[aux]!=p[i])
{
p[++aux]=p[i];
}
nr=aux+1;
for(int i=1; i<=n; i++)
{
coord[i].first=cb(coord[i].first);
coord[i].second=cb(coord[i].second);
}
for(int i=1; i<=m; i++)
{
d[i].x1=cb(d[i].x1);
d[i].y1=cb(d[i].y1);
d[i].x2=cb(d[i].x2);
d[i].y2=cb(d[i].y2);
}
sort(coord+1,coord+n+1);
build(1,1,n);///construim arborele de intervale in care adaugam fiecare punct in intervalele din care face parte
for(int i=1; i<=m; i++)
{
sol=0;
query(1,1,n,i);
cout<<sol<<'\n';
}
return 0;
}