Pagini recente » Cod sursa (job #401582) | Cod sursa (job #3188269) | Cod sursa (job #188454) | Cod sursa (job #399178)
Cod sursa(job #399178)
#include <fstream>
#include <algorithm>
using namespace std;
#define x first
#define y second
#define common\
int nst = (nod << 1), ndr = (nst | 1), mij = ((li + lf) >> 1)
const int MAX_N = 16005;
ifstream fin ("zoo.in");
ofstream fout ("zoo.out");
int N, M, *A[MAX_N << 2], st, dr, jos, sus;
pair <int, int> V[MAX_N];
void citire()
{
fin >> N;
for(int i = 1; i <= N; ++i)
fin >> V[i].x >> V[i].y;
sort(V+1, V+N+1);
}
void build(int nod, int li, int lf)
{
if(li == lf)
{
A[nod] = new int[3];
A[nod][A[nod][0] = 1] = V[li].y;
return;
}
common;
build(nst, li, mij);
build(ndr, mij+1, lf);
int Nl = A[nst][0], Nr = A[ndr][0], i = 1, j = 1;
A[nod] = new int[Nl + Nr + 3];
for(; i <= Nl && j <= Nr; )
A[nod][++A[nod][0]] = (A[nst][i] < A[ndr][j])? A[nst][i++] : A[ndr][j++];
for(; i <= Nl; ++i)
A[nod][++A[nod][0]] = A[nst][i];
for(; j <= Nr; ++j)
A[nod][++A[nod][0]] = A[ndr][j];
}
int query(int nod, int li, int lf)
{
if(st <= li && lf <= dr)
return upper_bound(A[nod]+1, A[nod]+A[nod][0]+1, sus) - lower_bound(A[nod]+1, A[nod]+A[nod][0]+1, jos);
common;
int rez = 0;
if(st <= mij) rez += query(nst, li, mij);
if(mij < dr) rez += query(ndr, mij+1, lf);
return rez;
}
int main()
{
citire();
build(1, 1, N);
fin >> M;
while(M--)
{
int x1, x2, y1, y2;
fin >> x1 >> y1 >> x2 >> y2;
st = lower_bound(V+1, V+N+1, make_pair(x1, y1)) - V;
dr = upper_bound(V+1, V+N+1, make_pair(x2, y2)) - V - 1;
jos = y1;
sus = y2;
if(st <= dr)
fout << query(1, 1, N) << "\n";
else
fout << "0\n";
}
}