Pagini recente » Cod sursa (job #3279753) | Cod sursa (job #1046894) | Cod sursa (job #3279257) | Cod sursa (job #916241) | Cod sursa (job #3162916)
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
ifstream cin("zoo.in");
ofstream cout("zoo.out");
int n,m,s[500010],k,i,last,sol;
pair<int, int>p[16010];
vector<int> A[500010];
struct coord_dreptunghiuri{
int x1,y1,x2,y2;
}d[100010];
int cauta(int x){
int st=0,dr=k-1;
while(st<=dr)
{
int mid=(st+dr)/2;
if(s[mid]==x)
return mid;
else
if(s[mid]<x)
st=mid+1;
else
dr=mid-1;
}
}
int build(int nod,int st,int dr){
for(int i=st;i<=dr;i++)
A[nod].push_back(p[i].second);
sort(A[nod].begin(),A[nod].end());
if(st<dr)
{
int mid=(st+dr)/2;
build(2*nod,st,mid);
build(2*nod+1,mid+1,dr);
}
}
int cauta_primul(int y,int nod){
int st=0;
int dr=A[nod].size()-1;
while(st <= dr)
{
int mid=(st+dr)/2;
if(A[nod][mid]>=y)
dr=mid-1;
else
st=mid+1;
}
return st;
}
int cauta_ultimul(int y,int nod){
int st=0;
int dr=A[nod].size()-1;
while(st <= dr)
{
int mid =(st+dr)/2;
if(A[nod][mid]<=y)
st=mid+1;
else
dr=mid-1;
}
return dr;
}
void query(int nod,int st,int dr,int poz){
if(st>dr)
return;
if(d[poz].x1<=p[st].first&&d[poz].x2>=p[dr].first)
sol+=(cauta_ultimul(d[poz].y2, nod)-cauta_primul(d[poz].y1, nod)+1);
else
{
if(st==dr)
return;
int mid=(st+dr)/2;
if (d[poz].x1<=p[mid].first)
query(2*nod,st,mid,poz);
if (d[poz].x2>=p[mid+1].first)
query(2*nod+1,mid+1,dr,poz);
}
}
int main()
{
cin>>n;
for(i=1;i<=n;i++)
{
cin>>p[i].first>>p[i].second;
s[++k]=p[i].first;
s[++k]=p[i].second;
}
cin>>m;
for(i=1;i<=m;i++)
{
cin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2;
s[k++]=d[i].x1;
s[k++]=d[i].y1;
s[k++]=d[i].x2;
s[k++]=d[i].y2;
}
///sortam vectorul s si eliminam dublurile
sort(s,s+k);
for(i=1;i<k;i++)
{
if(s[i]!=s[last])
s[++last]=s[i];
}
k=last+1;
///incepem normalizarea
for(i=1;i<=n;i++)
{
p[i].first=cauta(p[i].first);
p[i].second=cauta(p[i].second);
}
for(i=1;i<=m;i++)
{
d[i].x1=cauta(d[i].x1);
d[i].y1=cauta(d[i].y1);
d[i].x2=cauta(d[i].x2);
d[i].y2=cauta(d[i].y2);
}
sort(p+1,p+n+1);
build(1,1,n);
for(i=1;i<=m;i++)
{
sol=0;
query(1,1,n,i);
cout<<sol<<'\n';
}
return 0;
}