Pagini recente » Cod sursa (job #658858) | Cod sursa (job #2433168) | Cod sursa (job #720567) | Cod sursa (job #1040538) | Cod sursa (job #111063)
Cod sursa(job #111063)
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
#define pb push_back
#define vi vector <int>
const int maxn = 32001;
vi vectx;
vi arb[maxn * 4];
int n;
int m;
int x[maxn],y[maxn];
int nod;
int i;
int j;
int x1,x2,y1,y2;
int nr;
const int inf = 2000000010;
int bs1(int nod,int val)
{
int n = arb[nod].size() - 1;
if (n == -1) return 0;
int p;
int x = 0;
for(p = 1;p <= n;p <<= 1);
for(;p;p >>= 1)
if (x + p <= n)
{
if (arb[nod][x + p] <= val)
{
x += p;
}
}
if (val < arb[nod][x]) return x - 1;
return x;
}
int bs(int val)
{
int n = vectx.size() - 1;
int p;
int x = 0;
for(p = 1;p <= n;p <<= 1);
for(;p;p >>= 1)
if (x + p <= n)
{
if (vectx[x + p] <= val)
{
x += p;
}
}
if (val < vectx[x]) return x - 1;
return x;
}
int querry(int st,int dr,int nod)
{
int mid = (st + dr) / 2;
if (x1 <= st && x2 >= dr)
{
return bs1(nod,y2) - bs1(nod,y1 - 1);
}
if (mid >= x2) return querry(st,mid,nod * 2);
if (mid < x1) return querry(mid + 1,dr,nod * 2 + 1);
return querry(st,mid,nod * 2) + querry(mid + 1,dr,nod * 2 + 1);
}
void update(int st,int dr,int nod)
{
int mid = (st + dr) / 2;
if (st == dr && x1 == st)
{
arb[nod].pb(y[i]);
return ;
}
if (x1 <= mid) update(st,mid,nod * 2);
if (x1 > mid) update(mid + 1,dr,nod * 2 + 1);
arb[nod].pb(y[i]);
}
int main()
{
freopen("zoo.in","r",stdin);
freopen("zoo.out","w",stdout);
scanf("%d",&n);
vectx.pb(-inf - 1);
vectx.pb(-inf);
for(i = 1;i <= n; ++i)
{
scanf("%d %d",&x[i],&y[i]);
vectx.pb(x[i]);
}
vectx.pb(inf);
sort(vectx.begin(),vectx.end());
for(i = 1;i <= n; ++i)
{
x1 = bs(x[i]);
update(1,n + 2,1);
}
for(i = 1;i <= 4 * n; ++i)
{
sort(arb[i].begin(),arb[i].end());
}
scanf("%d",&m);
for(i = 1;i <= m; ++i)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
int aux = x1;
x1 = bs(x1);
if (aux != vectx[x1]) ++x1;
x2 = bs(x2);
printf("%d\n",querry(1,n + 2,1));
}
return 0;
}