Pagini recente » Cod sursa (job #2214715) | Cod sursa (job #2071175)
#include<fstream>
#include<algorithm>
#include<vector>
#define x first
#define y second
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int n, m, i1, i2, j1, j2, nr, i;
vector<int> a[64002];
pair<int, int> v[16002];
void build(int nod, int st, int dr){
if(st==dr)
a[nod].push_back(st);
else
{
int mid=(st+dr)/2;
build(2*nod, st, mid);
build(2*nod+1, mid+1, dr);
int i=0, j=0;
int s=nod*2, d=nod*2+1;
while(i<a[s].size()&&j<a[d].size())
{
if(v[a[s][i]].y<v[a[d][j]].y)
{
a[nod].push_back(a[s][i]);
i++;
}
else
{
a[nod].push_back(a[d][j]);
j++;
}
}
for(;i<a[s].size();i++)
a[nod].push_back(a[s][i]);
for(;j<a[d].size();j++)
a[nod].push_back(a[d][j]);
}
}
void query(int nod, int st, int dr)
{
if(i1<=v[st].x&&v[dr].x<=i2)
{
int p=0, u=a[nod].size()-1, mid, aux;
while(p<=u)
{
mid=(p+u)/2;
if(v[a[nod][mid]].y>=j1)
u=mid-1;
else
p=mid+1;
}
aux=p;
p=0;
u=a[nod].size()-1;
while(p<=u)
{
mid=(p + u)/2;
if(v[a[nod][mid]].y>j2)
u=mid-1;
else
p=mid+1;
}
nr+=(u-aux+1);
}
else
{
int mid=(st+dr)/2;
if(i1<=v[mid].x)
query(nod*2, st, mid);
if(i2>=v[mid+1].x)
query(nod*2+1, mid+1, dr);
}
}
int main(){
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort(v+1, v+n+1);
build(1, 1, n);
fin>>m;
for(i=1;i<=m;i++)
{
fin>>i1>>j1>>i2>>j2;
nr=0;
if(v[1].x>i2||v[n].x<i1)
{
fout<<0<<"\n";
continue;
}
query(1, 1, n);
fout<<nr<<"\n";
}
return 0;
}