Pagini recente » Cod sursa (job #1642462) | Cod sursa (job #2171959) | Cod sursa (job #2420243) | Cod sursa (job #919788) | Cod sursa (job #870862)
Cod sursa(job #870862)
# include <fstream>
# include <iostream>
# include <algorithm>
# define DIM 100003
# define MAX 20000
using namespace std;
struct pct{
int x, y, t;
friend bool operator < (const pct &a, const pct &b) {
if (a.x<b.x || (a.x==b.x && a.y<b.y) || (a.x==b.x && a.y==b.y && a.t<b.t))return true;
return false;
}
}v[5*DIM];
int n, m, s[DIM], a[MAX], y[MAX], N, Q;
void read ()
{
ifstream fin ("zoo.in");
fin>>n;
for(int i=1;i<=n;++i)
{
fin>>v[i].x>>v[i].y;
y[i+5]=v[i].y;
}
fin>>m;
N=n;
int x1, x2, y1, y2;
for(int i=1;i<=m;++i)
{
fin>>x1>>y1>>x2>>y2;
--x1;--y1;
v[N+1].x=x1;v[N+1].y=y1;v[N+1].t=2*i;
v[N+2].x=x2;v[N+2].y=y2;v[N+2].t=2*i;
v[N+3].x=x1;v[N+3].y=y2;v[N+3].t=2*i+1;
v[N+4].x=x2;v[N+4].y=y1;v[N+4].t=2*i+1;
N+=4;
}
}
void upd (int p)
{
while(p<=Q)
{
++a[p];
p+=p^(p&(p-1));
}
}
int query (int p)
{
int r = 0;
while(p>0)
{
r+=a[p];
p-=p^(p&(p-1));
}
return r;
}
int poz (int Y)
{
int r=0;
for(int st=1, dr=Q, mij=(st+dr)>>1;st<=dr;mij=(st+dr)>>1)
if (y[mij]==Y)
return mij;
else if (y[mij]<Y)
{
r=mij;
st=mij+1;
}
else
dr=mij-1;
return r;
}
void solve ()
{
sort(y+6, y+n+6);
for(int i=1;i<=n;++i)
if(i==1 || y[i+4]!=y[i+5])
y[++Q]=y[i+5];
sort(v+1, v+N+1);
for(int i=1;i<=N;++i)
if (!v[i].t)
upd(poz(v[i].y));
else
{
int q = v[i].t>>1;
s[q] += (q+q==v[i].t?1:-1) * query(poz(v[i].y));
}
}
int main ()
{
read ();
solve ();
freopen("zoo.out", "w", stdout);
for(int i=1;i<=m;++i)
printf("%d\n", s[i]);
return 0;
}