Pagini recente » Cod sursa (job #281041) | Cod sursa (job #1064844) | Cod sursa (job #504808) | Cod sursa (job #1125884) | Cod sursa (job #870871)
Cod sursa(job #870871)
# include <fstream>
# include <iostream>
# include <algorithm>
# define DIM 100003
# define MAX 20000
using namespace std;
struct pct{
int x, y, t;
inline 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[4*DIM], w[MAX];
int n, m, y[MAX], N, Q;
short a[MAX], s[DIM];
void read ()
{
ifstream fin ("zoo.in");
fin>>n;
fin.get();
char l[100];
for(int j=1;j<=n;++j)
{
fin.getline(l, 100);
int nr = 0, i=0, s=1;
for(i=0;l[i];++i)
{
if (l[i]=='-')
s=-1;
else if (l[i]>='0' && l[i]<='9')
nr=10*nr+l[i]-'0';
else
{
nr*=s;
w[j].x=nr;
break;
}
}
nr = 0;
s=1;
for(++i;l[i];++i)
if (l[i]=='-')
s=-1;
else if (l[i]>='0' && l[i]<='9')
nr=10*nr+l[i]-'0';
nr*=s;
w[j].y = nr;
y[j+5]=nr;
}
int x1, x2, y1, y2, p;
fin>>m;fin.get();
for(int j=1;j<=m;++j)
{
fin.getline(l, 100);
int nr = 0, i=0, s=1;
for(i=0;l[i];++i)
if (l[i]=='-')
s=-1;
else if (l[i]>='0' && l[i]<='9')
nr=10*nr+l[i]-'0';
else
{
nr*=s;
x1=nr;
break;
}
nr = 0;
s=1;
for(++i;l[i];++i)
if (l[i]=='-')
s=-1;
else if (l[i]>='0' && l[i]<='9')
nr=10*nr+l[i]-'0';
else
{
nr*=s;
y1=nr;
break;
}
nr = 0;
s=1;
for(++i;l[i];++i)
if (l[i]=='-')
s=-1;
else if (l[i]>='0' && l[i]<='9')
nr=10*nr+l[i]-'0';
else
{
nr*=s;
x2=nr;
break;
}
nr = 0;
s=1;
for(++i;l[i];++i)
if (l[i]=='-')
s=-1;
else if (l[i]>='0' && l[i]<='9')
nr=10*nr+l[i]-'0';
nr*=s;
y2=nr;
--x1;--y1;p=j<<1;
v[N+1].x=x1;v[N+1].y=y1;v[N+1].t=p;
v[N+2].x=x2;v[N+2].y=y2;v[N+2].t=p;
v[N+3].x=x1;v[N+3].y=y2;v[N+3].t=p+1;
v[N+4].x=x2;v[N+4].y=y1;v[N+4].t=p+1;
N+=4;
}
}
void upd (int p)
{
while(p<=Q)
{
++a[p];
p+=p^(p&(p-1));
}
}
short query (int p)
{
short 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);
sort(w+1, w+n+1);
int i=1, j=1;
for(;i<=N && j<=n;)
if (w[j]<v[i])
upd(poz(w[j].y)),
++j;
else
{
int q = v[i].t>>1;
s[q] += (q<<1==v[i].t?1:-1) * query(poz(v[i].y));
++i;
}
/*
while(i<=N)
{
int q = v[i].t>>1;
s[q] += (q<<1==v[i].t?1:-1) * query(poz(v[i].y));
++i;
}*/
}
int main ()
{
read ();
solve ();
freopen("zoo.out", "w", stdout);
for(int i=1;i<=m;++i)
printf("%d\n", s[i]);
return 0;
}