Pagini recente » Cod sursa (job #1808614) | Cod sursa (job #161663) | Cod sursa (job #1882292) | Cod sursa (job #1174883) | Cod sursa (job #870854)
Cod sursa(job #870854)
# include <fstream>
# include <iostream>
# include <vector>
# include <algorithm>
# define DIM 100303
# 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, M, xx;
vector< pair<int, int> >X, Y, P, A[MAX], B[MAX], C[MAX], D[MAX];
void read ()
{
ifstream fin ("zoo.in");
fin>>n;
fin.get();
int x, y;
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;
X.pb(mp(nr, j));
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;
Y.pb(mp(nr, j));
}
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;
X.pb(mp(nr, n+2*j-1));
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;
Y.pb(mp(nr, n+2*j-1));
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;
X.pb(mp(nr, n+2*j));
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;
Y.pb(mp(nr, n+2*j));
}
}
void uniform()
{
sort(X.begin(),X.end());
sort(Y.begin(),Y.end());
M=0;
for(int i=0;i<X.size();++i)
{
if (i==0 || X[i-1].fs!=X[i].fs)
++M;
x[X[i].sc] = M;
}
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;
}
void comp(int xxx)
{
while(xx<=xxx)
{
for(vector< pair<int,int> >::iterator I=A[xx].begin();I!=A[xx].end();++I)
s[I->sc]+=query(I->fs);
for(vector< pair<int,int> >::iterator I=B[xx].begin();I!=B[xx].end();++I)
s[I->sc]+=query(I->fs);
for(vector< pair<int,int> >::iterator I=C[xx].begin();I!=C[xx].end();++I)
s[I->sc]-=query(I->fs);
for(vector< pair<int,int> >::iterator I=D[xx].begin();I!=D[xx].end();++I)
s[I->sc]-=query(I->fs);
++xx;
}
}
void solve ()
{
for(int i=1;i<=n;++i)
P.pb(mp(x[i],y[i]));
for(int i=1;i<=m;++i)
{
int j = n+2*i-1;
A[x[j]-1].pb(mp(y[j]-1, i));
B[x[j+1]].pb(mp(y[j+1], i));
C[x[j]-1].pb(mp(y[j+1], i));
D[x[j+1]].pb(mp(y[j]-1, i));
}
sort(P.begin(),P.end());
comp(P[0].fs - 1);
for(int i=0;i<P.size();++i)
{
if (i>0 && P[i-1].fs != P[i].fs)
comp(P[i-1].fs);
upd(P[i].sc);
}
comp(M);
}
int main ()
{
read ();
uniform ();
//solve ();
freopen("zoo.out", "w", stdout);
for(int i=1;i<=m;++i)
printf("%d\n", s[i]);
return 0;
}