Pagini recente » Cod sursa (job #1071048) | Cod sursa (job #1128550) | Cod sursa (job #316128) | Cod sursa (job #2546133) | Cod sursa (job #1153423)
#include <fstream>
#include <vector>
#include <algorithm>
#define N 65000
using namespace std;
ifstream fin ("zoo.in");
ofstream fout ("zoo.out");
struct data {
int x;
int y;
}v[20005];
vector <int> a[N];
int X1,Y1,X2,Y2,i,j,mid,dr,st,sum,A,b,n,m;
void interclasare (int I, int J, int K){
a[I].clear();
int n=a[J].size()-1;
int m=a[K].size()-1;
int i=0,j=0;
while (i<=n && j<=m) {
if (a[J][i]<a[K][j]){
a[I].push_back(a[J][i]);
i++;
}else{
a[I].push_back(a[K][j]);
j++;
}
}
for (;i<=n;i++)
a[I].push_back(a[J][i]);
for (;j<=m;j++)
a[I].push_back(a[K][j]);
}
void update (int nod, int st, int dr){
if (st==dr) {
a[nod].push_back(v[i].y);
return;
}
int mid=(st+dr)/2;
if (i<=mid)
update (nod*2,st,mid);
else
if (i>mid)
update (nod*2+1,mid+1,dr);
if (a[2*nod].size () !=0 && a[2*nod+1].size()!=0)
interclasare (nod,nod*2,nod*2+1);
}
void query (int nod, int st, int dr) {
if (A<=st && b>=dr) {
int p=0;
int u=a[nod].size()-1;
while (p<=u) {
mid=(p+u)/2;
if (a[nod][mid]>=Y1)
u=mid-1;
else
p=mid+1;
}
int qs=p;
p=0;u=a[nod].size()-1;
while (p<=u) {
mid=(p+u)/2;
if (a[nod][mid]>Y2)
u=mid-1;
else
p=mid+1;
}
int qd=u;
sum+=(qd-qs+1);
return;
}
if(st==dr)
return;
int mid=(st+dr)/2;
if (A<=mid)
query(nod*2,st,mid);
if (b>mid)
query(nod*2+1,mid+1,dr);
}
bool cmp (const data &a, const data &b) {
return a.x<b.x;
}
int main () {
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort (v+1,v+n+1,cmp);
for (i=1;i<=n;i++)
update (1,1,n);
fin>>m;
while (m--) {
fin>>X1>>Y1>>X2>>Y2;
st=1;dr=n;
while (st<=dr) {
mid=(st+dr)/2;
if (v[mid].x>=X1)
dr=mid-1;
else
st=mid+1;
}
A=st;
st=1;dr=n;
while (st<=dr) {
mid=(st+dr)/2;
if (v[mid].x>X2)
dr=mid-1;
else
st=mid+1;
}
b=dr;
sum=0;
query(1,1,n);
fout<<sum<<"\n";
}
return 0;
}