Pagini recente » Cod sursa (job #3176261) | Cod sursa (job #1129062) | Cod sursa (job #354885) | Cod sursa (job #251198) | Cod sursa (job #1002833)
#include<vector>
#include<set>
#include<cassert>
#include<map>
#include<cstdio>
#include<algorithm>
using namespace std;
struct MyQuery {int x1,y1,x2,y2,ans;} q[100005];
struct Solvable_query {int x,y,ind;bool type,semn;} v[416005];
int aib[500005];
int query(int x)
{
int ans=0;
for(int i=x;i;i-=(i&(-i)))
ans+=aib[i];
return ans;
}
class cmp
{
public: inline bool operator()(const Solvable_query &a,const Solvable_query &b)
{
if(a.x==b.x)
return a.type<b.type;
return a.x<b.x;
}
};
set<int> S;
const int hmod=63013;
vector< pair<int,int> > H[hmod];
int normalize(int n)
{
int ans=0,ind=0;
for(int i=1;i<=n;i++)
S.insert(v[i].y);
for(set<int>::iterator it=S.begin();it!=S.end();it++)
H[(*it>0?*it:-*it)%hmod].push_back(make_pair(*it,++ind));
for(int i=1;i<=n;i++)
{
int h=(v[i].y>0?v[i].y:-v[i].y)%hmod;
for(vector< pair<int,int> >::iterator it=H[h].begin();it!=H[h].end();it++)
if(it->first==v[i].y)
{
v[i].y=it->second;
break;
}
ans=max(ans,v[i].y);
}
return ans;
}
char buf[7000000];int crs=0,sz=7000000;
void getInt(int &n)
{
n=0;
while(crs<sz && buf[crs]!='-' && !('0'<=buf[crs] && buf[crs]<='9')) crs++;
int semn=1;
if(buf[crs]=='-') semn=-1,crs++;
while(crs<sz && ('0'<=buf[crs] && buf[crs]<='9')) {n=n*10+buf[crs]-'0';crs++;}
n*=semn;
}
int main()
{
freopen("zoo.in","r",stdin);
freopen("zoo.out","w",stdout);
int N,n,m;
fread(buf,1,sz,stdin);
getInt(n);N=n;
for(int i=1;i<=n;i++)
{getInt(v[i].x);getInt(v[i].y);v[i].type=0;}
getInt(m);
for(int i=1;i<=m;i++)
{
getInt(q[i].x1);
getInt(q[i].y1);
getInt(q[i].x2);
getInt(q[i].y2);
v[++N].x=q[i].x2;v[N].y=q[i].y2;v[N].type=1;v[N].ind=i;v[N].semn=true;
v[++N].x=q[i].x2;v[N].y=q[i].y1-1;v[N].type=1;v[N].ind=i;v[N].semn=false;
v[++N].x=q[i].x1-1;v[N].y=q[i].y2;v[N].type=1;v[N].ind=i;v[N].semn=false;
v[++N].x=q[i].x1-1;v[N].y=q[i].y1-1;v[N].type=1;v[N].ind=i;v[N].semn=true;
}
int MAX=normalize(N);
sort(v+1,v+N+1,cmp());
for(int i=1;i<=N;i++)
if(v[i].type==false)
{
for(int I=v[i].y;I<=MAX;I+=(I&(-I)))
aib[I]++;
}
else
q[v[i].ind].ans+=(v[i].semn?1:-1)*query(v[i].y);
for(int i=1;i<=m;i++)
printf("%d\n",q[i].ans);
return 0;
}