Pagini recente » Cod sursa (job #1294676) | Cod sursa (job #936992) | Cod sursa (job #1203925) | Cod sursa (job #2989306) | Cod sursa (job #1153997)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
vector< int > A[65005];
int n,m,i,p,u,mid,sol,x,xx,y,yy,a,b,stanga,dreapta;
struct point {
int x;
int y;
} v[20005];
void query(int nod,int st,int dr);
void update(int nod,int st,int dr);
void intercl(int nod);
bool cmp(const point &a, const point &b) {
return a.x<b.x;
}
int main() {
ifstream f("zoo.in");
ofstream g("zoo.out");
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++)
update(1,1,n);
f>>m;
while(m--) {
f>>x>>y>>xx>>yy;
p=1;u=n;
while(p<=u) {
mid=p+(u-p)/2;
if(v[mid].x>=x)
u=mid-1;
else
p=mid+1;
}
a=p;
p=1;u=n;
while(p<=u) {
mid=p+(u-p)/2;
if(v[mid].x>xx)
u=mid-1;
else
p=mid+1;
}
b=u;
sol=0;
query(1,1,n);
g<<sol<<"\n";
}
return 0;
}
void intercl(int nod) {
A[nod].clear();
int m=A[nod*2].size()-1;
int n=A[nod*2+1].size()-1;
int i=0,j=0;
while(i<=m && j<=n) {
if(A[nod*2][i]<A[nod*2+1][j]) {
A[nod].push_back(A[nod*2][i]);
i++;
}
else {
A[nod].push_back(A[nod*2+1][j]);
j++;
}
}
for(;i<=m;i++)
A[nod].push_back(A[nod*2][i]);
for(;j<=n;j++)
A[nod].push_back(A[nod*2+1][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
update(nod*2+1,mid+1,dr);
if(!A[2*nod].empty() && !A[2*nod+1].empty())
intercl(nod);
return;
}
void query(int nod, int st, int dr) {
if(a<=st && b>=dr) {
int p=0,u=A[nod].size()-1;
int mid;
while(p<=u) {
mid=(p+u)/2;
if(A[nod][mid]>=y)
u=mid-1;
else
p=mid+1;
}
stanga=p;
p=0;
u=A[nod].size()-1;
while(p<=u) {
mid=(p+u)/2;
if(A[nod][mid]>yy)
u=mid-1;
else
p=mid+1;
}
dreapta=u;
sol+=dreapta-stanga+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);
return;
}