Pagini recente » Cod sursa (job #3192313) | Cod sursa (job #1687475) | Cod sursa (job #2948218) | Cod sursa (job #1990017) | Cod sursa (job #2879861)
#include <bits/stdc++.h>
#define z(n) ((n^(n-1))&n)
#define nmax 16005
#define mmax 100005
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int aib[nmax],k,n,m;
int i,j;
void up(const int &p,const int &v)
{
if(p==0) return;
for(j=p;j<=n;j+=z(j)) aib[j]+=v;
}
int qer(const int &p)
{
int ans=0;
for(j=p;j>0;j-=z(j)) ans+=aib[j];
return ans;
}
struct nod{
int x,y,c=0,id;
nod(){}
nod(int x, int y, int c)
{
this->x=x;
this->y=y;
this->c=c;
}
};
nod v[nmax+mmax*4];
int ix[nmax+mmax*4];
int ans[mmax];
int srt[nmax];
bool cmpx(const int &a, const int &b)
{
return v[a].x<v[b].x||((v[a].x==v[b].x&&v[a].y<v[b].y)||(v[a].x==v[b].x&&v[a].y==v[b].y&&v[a].c==0));
}
bool cmpy(const int &a, const int &b)
{
return v[a].y<v[b].y;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
f.tie(NULL);
f>>n;
for(i=1;i<=n;i++)
{
++k; f>>v[k].x>>v[k].y;
ix[k]=k;
}
f>>m;
int a,b,c,d;
sort(ix+1,ix+k+1,cmpy);
for(i=1;i<=k;i++) {v[ix[i]].id=i;srt[i]=v[ix[i]].y;}
for(i=1;i<=m;i++)
{
f>>a>>b>>c>>d;
v[++k]=nod(a-1,b-1,i); ix[k]=k;
v[++k]=nod(a-1,d,-i); ix[k]=k;
v[++k]=nod(c,b-1,-i); ix[k]=k;
v[++k]=nod(c,d,i); ix[k]=k;
}
/*for(i=1;i<=k;i++) cout<<ix[i]<<' ';
cout<<'\n';
for(i=1;i<=k;i++) cout<<ix[i]<<' ';
cout<<'\n';*/
sort(ix+1,ix+k+1,cmpx);
for(i=1;i<=k;i++)
{
//cout<<ix[i]<<' ';
if(v[ix[i]].c==0) up(v[ix[i]].id,1);
if(v[ix[i]].c<0) ans[-v[ix[i]].c]-=qer(upper_bound(srt+1,srt+n+1,v[ix[i]].y)-srt-1);
if(v[ix[i]].c>0) ans[v[ix[i]].c]+=qer(upper_bound(srt+1,srt+n+1,v[ix[i]].y)-srt-1);
}
for(i=1;i<=m;i++) g<<ans[i]<<'\n';
return 0;
}