Pagini recente » Cod sursa (job #2454909) | Cod sursa (job #461874) | Cod sursa (job #2053405) | Cod sursa (job #1436074) | Cod sursa (job #1229126)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct points
{
int x,y;
int indice;
bool ok;
};
struct drept
{
int x,y,w,z;
};
const int NMAX=16005;
const int MMAX=100005;
int n,m,sol[MMAX],AIB[NMAX];
vector<points>v[NMAX];
vector<points>::iterator it;
points a[NMAX],linie[MMAX],coloana[MMAX];
drept b[MMAX];
inline bool cmp1(const points A,const points B)
{
return A.x<B.x;
}
inline bool cmp2(const points A,const points B)
{
return A.y<B.y;
}
inline int zeros(int x)
{
return x^(x&(x-1));
}
inline void UPDATE(int poz,int val)
{
for (;poz<=n;poz+=zeros(poz)) AIB[poz]+=val;
}
inline int QUERY(int poz)
{
int i,rez=0;
for (i=poz;i>=1;i-=zeros(i)) rez+=AIB[i];
return rez;
}
int main()
{
int i,aux,st,dr,mij;
points d;
fin>>n;
for (i=1;i<=n;i++) fin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp1);
for (i=1;i<=n;i++) a[i].indice=i;
fin>>m;
for (i=1;i<=m;i++)
{
fin>>b[i].x>>b[i].y>>b[i].w>>b[i].z;
st=1;dr=n;
while (st<=dr)
{
mij=(st+dr)>>1;
if (a[mij].x>=b[i].x) {linie[i].x=mij;dr=mij-1;}
else st=mij+1;
}
st=1;dr=n;
while (st<=dr)
{
mij=(st+dr)>>1;
if (a[mij].x<=b[i].w) {linie[i].y=mij;st=mij+1;}
else dr=mij-1;
}
}
sort(a+1,a+n+1,cmp2);
for (i=1;i<=m;i++)
{
st=1;dr=n;
while (st<=dr)
{
mij=(st+dr)>>1;
if (a[mij].y>=b[i].y) {coloana[i].x=mij;dr=mij-1;}
else st=mij+1;
}
st=1;dr=n;
while (st<=dr)
{
mij=(st+dr)>>1;
if (a[mij].y<=b[i].z) {coloana[i].y=mij;st=mij+1;}
else dr=mij-1;
}
if (linie[i].x!=0 && linie[i].y!=0 && linie[i].x<=linie[i].y)
if (coloana[i].x!=0 && coloana[i].y!=0 && coloana[i].x<=coloana[i].y)
{
d.x=linie[i].x;
d.y=linie[i].y;
d.indice=i;
d.ok=0;
v[coloana[i].x - 1].push_back(d);
d.ok=1;
v[coloana[i].y].push_back(d);
}
}
for (i=1;i<=n;i++)
{
UPDATE(a[i].indice,1);
for (it=v[i].begin();it!=v[i].end();it++)
{
d=*it;
aux=QUERY(d.y)-QUERY(d.x - 1);
if (d.ok==0) sol[d.indice]-=aux;
else sol[d.indice]+=aux;
}
}
for (i=1;i<=m;i++) fout<<sol[i]<<"\n";
return 0;
}