Pagini recente » Cod sursa (job #726518) | Cod sursa (job #81104) | Cod sursa (job #1414899) | Cod sursa (job #1091443) | Cod sursa (job #1224424)
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 16010;
const int M = 100010;
const int inf = 2000000001;
int n,m;
ifstream fin("zoo.in");
char parse[1 << 20], *now;
inline void verify()
{
if (*now == 0)
{
fin.get(parse, (1 << 20), '\0');
now = parse;
}
}
int get()
{
while (*now != '-' && (*now < '0' || *now > '9'))
{
++now;
verify();
}
bool neg = false;
if (*now == '-')
{
neg = true;
++now;
verify();
}
int num = 0;
while (*now >= '0' && *now <= '9')
{
num = num * 10 + (*now - '0');
++now;
verify();
}
if (neg) num *= -1;
return num;
}
struct query
{
int x,y,sgn,ord;
};
query make(int x,int y,int sgn,int ord)
{
query q;
q.x = x;
q.y = y;
q.sgn = sgn;
q.ord = ord;
return q;
}
bool cmp(query a,query b)
{
return a.x < b.x || ( a.x == b.x && a.sgn == 0 && b.sgn != 0 );
}
vector<query> v;
vector<int> ys;
int AIB[N],ans[M];
void add(int x)
{
if ( x == 0 ) return;
for (int i=x;i<N;i+=(i&(-i)))
AIB[i]++;
}
int ask(int x)
{
if ( x == 0 ) return 0;
int ans = 0;
for (int i=x;i>0;i-=(i&(-i)))
ans += AIB[i];
return ans;
}
int main()
{
now = parse;
verify();
freopen("zoo.out","w",stdout);
n = get();
for (int i=1,x,y;i<=n;++i)
{
x = get();
y = get();
ys.push_back(y);
v.push_back( make(x,y,0,0) );
}
m = get();
for (int i=1,x,y,x2,y2;i<=m;++i)
{
x = get();
y = get();
x2 = get();
y2 = get();
v.push_back( make(x-1,y-1,1,i) );
v.push_back( make(x2,y-1,-1,i) );
v.push_back( make(x-1,y2,-1,i) );
v.push_back( make(x2,y2,1,i) );
}
sort(ys.begin(),ys.end());
ys.erase( unique(ys.begin(),ys.end()) , ys.end() );
sort(v.begin(),v.end(),cmp);
for (size_t i=0;i<v.size();++i)
{
query a = v[i];
int y = upper_bound(ys.begin(),ys.end(),a.y) - ys.begin();
if ( y > int(ys.size()) ) y = ys.size();
if ( a.sgn == 0 )
add(y);
else
ans[a.ord] += ask(y) * a.sgn;
}
for (int i=1;i<=m;++i)
printf("%d\n",ans[i]);
}