Pagini recente » Cod sursa (job #973041) | Cod sursa (job #731783) | Cod sursa (job #1727209) | Cod sursa (job #801393) | Cod sursa (job #870785)
Cod sursa(job #870785)
# include <fstream>
# include <iostream>
# include <vector>
# include <algorithm>
# define DIM 100003
# define MAX 120000
# define pb push_back
# define mp make_pair
# define fs first
# define sc second
using namespace std;
int n, m, x[3*DIM], y[3*DIM], s[DIM], a[MAX], N, v[5*DIM], V;
vector< pair<int, int> >X, Y;
vector< pair<pair<int,int>, int> > P;
void read ()
{
ifstream fin ("zoo.in");
fin>>n;
int x, y;
for(int i=1;i<=n;++i)
{
fin>>x>>y;
X.pb(mp(x, i));
Y.pb(mp(y, i));
}
fin>>m;
for(int i=1;i<=2*m;++i)
{
fin>>x>>y;
X.pb(mp(x, n+i));
Y.pb(mp(y, n+i));
}
}
void uniform()
{
sort(X.begin(),X.end());
sort(Y.begin(),Y.end());
N=0;
for(int i=0;i<X.size();++i)
{
if (i==0 || X[i-1].fs!=X[i].fs)
++N;
x[X[i].sc] = N;
}
N=0;
for(int i=0;i<Y.size();++i)
{
if (i==0 || Y[i-1].fs!=Y[i].fs)
++N;
y[Y[i].sc] = N;
}
}
void upd (int p)
{
while(p<=N)
{
++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;
}
inline bool cmp (int i, int j)
{
return P[i]<P[j];
}
void solve ()
{
for(int i=1;i<=n;++i)
{
P.pb(mp(mp(x[i],y[i]), i));
v[++V]=V-1;
}
for(int i=1;i<=m;++i)
{
int j = n+2*i-1;
P.pb(mp(mp(x[j]-1,y[j]-1), n+1+4*i-4));
v[++V]=V-1;
P.pb(mp(mp(x[j+1], y[j+1]), n+1+4*i-2));
v[++V]=V-1;
P.pb(mp(mp(x[j]-1, y[j+1]), n+1+4*i-3));
v[++V]=V-1;
P.pb(mp(mp(x[j+1], y[j]-1), n+1+4*i-1));
v[++V]=V-1;
}
sort(v+1, v+V+1, cmp);
for(int i=1;i<=V;++i)
{
pair<pair<int,int>, int> I = P[v[i]];
if (I.sc <= n)
upd(I.fs.sc);
else
{
int q = (I.sc - n-1)/4+1, o = (I.sc - n-1)%2;
s[q] += (o?-1:1)*query(I.fs.sc);
}
}
}
int main ()
{
read ();
uniform ();
solve ();
freopen("zoo.out", "w", stdout);
for(int i=1;i<=m;++i)
printf("%d\n", s[i]);
return 0;
}