Pagini recente » Cod sursa (job #2023029) | Cod sursa (job #621279) | Cod sursa (job #61364) | Cod sursa (job #1222974) | Cod sursa (job #2023566)
#include <bits/stdc++.h>
#define Nmax 16005
#define Mmax 100005
#define LSB(x) ((x ^ (x - 1)) & x)
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct point
{
int x,y;
};
struct event
{
int t;
int idx;
int x, y1, y2;
};
event E[2 * Mmax];
point P[Nmax];
int ESIZE;
int N, M;
int ans[Mmax];
int normalize[2 * Mmax + Nmax + 55];
int aib[2 * Mmax + Nmax + 55];
int L;
bool qx(point a, point b)
{
return make_pair(a.x, a.y) < make_pair(b.x, b.y);
}
bool qxE(event a, event b)
{
return a.x < b.x;
}
void update(int pos, int val)
{
for(; pos <= L; pos += LSB(pos))
aib[pos] += val;
}
int query(int pos)
{
int ret = 0;
for(; pos >= 1; pos -= LSB(pos))
ret += aib[pos];
return ret;
}
int main()
{
fin >> N;
for(int i = 1; i <= N; i++)
fin >> P[i].x >> P[i].y, normalize[++L] = P[i].y;
fin >> M;
for(int i = 1; i <= M; i++)
{
int x1, y1, x2, y2;
fin >> x1 >> y1 >> x2 >> y2;
E[++ESIZE] = {-1, i, x1 - 1, y1, y2};
E[++ESIZE] = {1, i, x2, y1, y2};
normalize[++L] = y1;
normalize[++L] = y2;
}
sort(normalize + 1, normalize + L + 1);
int newL = 1;
for(int i = 2; i <= L; i++)
if(normalize[newL] != normalize[i])
normalize[++newL] = normalize[i];
L = newL;
for(int i = 1; i <= N; i++)
P[i].y = lower_bound(normalize + 1, normalize + L + 1, P[i].y) - normalize;
for(int i = 1; i <= ESIZE; i++)
{
E[i].y1 = lower_bound(normalize + 1, normalize + L + 1, E[i].y1) - normalize;
E[i].y2 = lower_bound(normalize + 1, normalize + L + 1, E[i].y2) - normalize;
}
sort(P + 1, P + N + 1, qx);
sort(E + 1, E + ESIZE + 1, qxE);
int j = 1;
for(int i = 1; i <= ESIZE; i++)
{
for(; j <= N && P[j].x <= E[i].x; j++)
update(P[j].y, 1);
ans[E[i].idx] += E[i].t * (query(E[i].y2) - query(E[i].y1 - 1));
}
for(int i = 1; i <= M; i++)
fout << ans[i] << "\n";
return 0;
}