Pagini recente » Cod sursa (job #2890209) | Cod sursa (job #1253788) | Cod sursa (job #58559) | Cod sursa (job #419336) | Cod sursa (job #1082312)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct coord
{
int x, y;
};
coord P[4 * 16002];
int N, M;
int x1, x2, y1, y2;
int sol;
vector<int> V[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) / 2;
update(2 * nod, lt, mid);
update(2 * nod + 1, mid + 1, rt);
interclasare(nod);
}
void caut_bin(int nod)
{
int sol1, sol2;
int lt, rt, mid;
lt = 0;
rt = V[nod].size();
while (rt - lt > 1)
{
mid = (lt + rt) / 2;
if (V[nod][mid] < y1) lt = mid;
else rt = mid;
}
sol1 = lt;
lt = 0;
rt = V[nod].size();
while (rt - lt > 1)
{
mid = (lt + rt) / 2;
if (V[nod][mid] < y2) lt = mid;
else rt = mid;
}
sol2 = rt;
sol = sol1 - sol2 + 1;
}
void question(int nod, int lt, int rt)
{
if (x1 <= lt && rt <= x2)
{
caut_bin(nod);
return;
}
int mid = (lt + rt) / 2;
if (x1 <= mid) question(2 * nod, lt, mid);
if (mid < x2) 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;
question(1, 1, N);
fout << sol << '\n';
}
fin.close();
fout.close();
return 0;
}