Pagini recente » Cod sursa (job #2715135) | Cod sursa (job #2383809) | Cod sursa (job #1813346) | Cod sursa (job #2062386) | Cod sursa (job #1140062)
#include <cstdio>
#include <cassert>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("zoo.in");
char parse[1 << 20], *now;
inline void verify()
{
if (*now == 0)
{
fin.get(parse, (1 << 20), '\0');
now = parse;
}
}
int get()
{
while (*now != '-' && (*now < '0' || *now > '9'))
{
++now;
verify();
}
bool neg = false;
if (*now == '-')
{
neg = true;
++now;
verify();
}
int num = 0;
while (*now >= '0' && *now <= '9')
{
num = num * 10 + (*now - '0');
++now;
verify();
}
if (neg) num *= -1;
return num;
}
int N, M;
int X[16002], Y[16002];
int Yw1[100002], Yw2[100002];
int yes[16002], nowY;
int Yn[16002];
int Xn[200002], Pn[200002];
int pos[16002], posV[200002];
int AIB[16002];
int result[100002];
void update(int pnow, int val)
{
for (; pnow <= nowY; pnow += pnow & -pnow)
AIB[pnow] += val;
}
int query(int pnow)
{
int sum = 0;
for (; pnow >= 1; pnow -= pnow & -pnow)
sum += AIB[pnow];
return sum;
}
bool compareV(const int& i1, const int& i2)
{
return Xn[i1] < Xn[i2];
}
bool compareY(const int& i1, const int& i2)
{
return Y[i1] < Y[i2];
}
bool compare(const int& i1, const int& i2)
{
return X[i1] < X[i2];
}
int main()
{
freopen("zoo.out", "w", stdout);
now = parse;
verify();
N = get();
for (int i = 1; i <= N; ++i)
{
X[i] = get();
Y[i] = get();
yes[++yes[0]] = i;
pos[i] = i;
}
sort(yes + 1, yes + yes[0] + 1, compareY);
for (int i = 1; i <= yes[0]; ++i)
{
++nowY;
Yn[++Yn[0]] = Y[yes[i]];
int ybase = Y[yes[i]];
while (Y[yes[i]] == ybase)
{
Y[yes[i]] = nowY;
++i;
}
--i;
}
M = get();
for (int i = 1, xn1, yn1, xn2, yn2; i <= M; ++i)
{
xn1 = get();
yn1 = get();
xn2 = get();
yn2 = get();
int step, yw1 = 0, yw2 = 0;
for (step = (1 << 13); step; step >>= 1)
if (yw1 + step <= Yn[0] && Yn[yw1 + step] < yn1)
yw1 += step;
++yw1;
for (step = (1 << 13); step; step >>= 1)
if (yw2 + step <= Yn[0] && Yn[yw2 + step] <= yn2)
yw2 += step;
Yw1[i] = yw1 - 1;
Yw2[i] = yw2;
Xn[2 * i - 1] = xn1 - 1;
Pn[2 * i - 1] = -i;
posV[2 * i - 1] = 2 * i - 1;
Xn[2 * i] = xn2;
Pn[2 * i] = i;
posV[2 * i] = 2 * i;
}
sort(posV + 1, posV + 2 * M + 1, compareV);
sort(pos + 1, pos + N + 1, compare);
int pnow = 1;
for (int i = 1; i <= 2 * M; ++i)
{
if (Yw1[Pn[posV[i]]] - 1 > Yw2[Pn[posV[i]]]) continue;
while (pnow <= N && X[pos[pnow]] <= Xn[posV[i]])
{
update(Y[pos[pnow]], 1);
++pnow;
}
int pn = Pn[posV[i]];
if (pn > 0)
result[pn] += query(Yw2[pn]) - query(Yw1[pn] - 1);
else
{
pn = -pn;
result[pn] -= query(Yw2[pn]) - query(Yw1[pn] - 1);
}
}
for (int i = 1; i <= M; ++i)
printf("%d\n", result[i]);
fin.close();
}