Pagini recente » Cod sursa (job #2098319) | Cod sursa (job #1847811) | Cod sursa (job #3156067) | Cod sursa (job #2036316) | Cod sursa (job #998612)
Cod sursa(job #998612)
#include<set>
#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,type;bool semn;} v[416005];
int aib[500000];
void update(int x,int n)
{
for(int i=x;i<=n;i+=(i&(-i)))
aib[i]++;
}
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;
}
};
int aux[416005];
map<int,int> NRM;
int normalize(int n)
{
int ans=0,ind=0;
for(int i=1;i<=n;i++)
aux[i]=v[i].y;
sort(aux+1,aux+n+1);
for(int i=1;i<=n;i++)
if(i==1 || aux[i]!=aux[i-1])
NRM[aux[i]]=i;
for(int i=1;i<=n;i++)
{
v[i].y=NRM[v[i].y];
ans=max(ans,v[i].y);
}
return ans;
}
int main()
{
freopen("zoo.in","r",stdin);
freopen("zoo.out","w",stdout);
int n,m;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{scanf("%d%d",&v[i].x,&v[i].y);v[i].type=0;}
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2);
int N=n;
for(int i=1;i<=m;i++)
{
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)
update(v[i].y,MAX);
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;
}