Pagini recente » Cod sursa (job #1709120) | Cod sursa (job #2192685) | Cod sursa (job #1984091) | Cod sursa (job #2497455) | Cod sursa (job #1083000)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct coord
{
int x, y;
};
coord P[16002];
int N, M;
int X1, X2, Y1, Y2;
int start, finish;
int sol;
vector<int> V[4 * 16002];
bool cmp(coord A, coord B)
{
return (A.x < B.x || (A.x == B.x && A.y < B.y));
}
void interclasare(int nod)
{
vector<int>::iterator f1, f2;
f1 = V[2 * nod].begin();
f2 = V[2 * nod + 1].begin();
while (f1 != V[2 * nod].end() && f2 != V[2 * nod + 1].end())
{
while (*f1 < *f2 && f1 != V[2 * nod].end())
{
V[nod].push_back(*f1);
++f1;
}
while (*f2 <= *f1 && f2 != V[2 * nod + 1].end())
{
V[nod].push_back(*f2);
++f2;
}
}
if (f1 == V[2 * nod].end())
{
while (f2 != V[2 * nod + 1].end())
{
V[nod].push_back(*f2);
++f2;
}
}
else if (f2 == V[2 * nod + 1].end())
{
while (f1 != V[2 * nod].end())
{
V[nod].push_back(*f1);
++f1;
}
}
}
void update(int nod, int lt, int rt)
{
if (lt == rt)
{
V[nod].push_back(P[lt].y);
return;
}
int mid = (lt + rt) >> 1;
update(2 * nod, lt, mid);
update(2 * nod + 1, mid + 1, rt);
interclasare(nod);
}
int cb(int nod)
{
int lt, rt;
int sol1, sol2;
lt = -1;
rt = V[nod].size();
while (rt - lt > 1)
{
int mid = (lt + rt) >> 1;
if (V[nod][mid] > Y2) rt = mid;
else lt = mid;
}
sol1 = lt;
lt = -1;
rt = V[nod].size();
while (rt - lt > 1)
{
int mid = (lt + rt) >> 1;
if (V[nod][mid] < Y1) lt = mid;
else rt = mid;
}
sol2 = rt;
return sol1 - sol2 + 1;
}
int cb_ub()
{
int lt = 0, rt = N + 1;
while (rt - lt > 1)
{
int mid = (lt + rt) >> 1;
if (P[mid].x > X2) rt = mid;
else lt = mid;
}
return lt;
}
int cb_lb()
{
int lt = 0, rt = N + 1;
while (rt - lt > 1)
{
int mid = (lt + rt) >> 1;
if (P[mid].x < X1) lt = mid;
else rt = mid;
}
return rt;
}
void question(int nod, int lt, int rt)
{
if (start <= lt && rt <= finish)
{
sol += cb(nod);
return;
}
if (lt == rt) return;
int mid = (lt + rt) >> 1;
if (start <= mid) question(2 * nod, lt, mid);
if (mid < finish) question(2 * nod + 1, mid + 1, rt);
}
int main()
{
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> P[i].x >> P[i].y;
sort(P + 1, P + N + 1, cmp);
update(1, 1, N);
fin >> M;
for (int i = 1; i <= M; ++i)
{
fin >> X1 >> Y1 >> X2 >> Y2;
sol = 0;
start = cb_lb();
finish = cb_ub();
question(1, 1, N);
fout << sol << '\n';
}
fin.close();
fout.close();
return 0;
}