Pagini recente » Cod sursa (job #482198) | Cod sursa (job #404826) | Cod sursa (job #262632) | Cod sursa (job #956114) | Cod sursa (job #1750750)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <unordered_map>
#define MAXN 16064
#define MAXM 100050
#define DIM 300000
using namespace std;
struct punct
{
int x, y;
punct(int x = 0, int y = 0) : x(x), y(y) { }
};
int n, m, cursor;
unsigned int MAX_VAL;
char buf[DIM];
punct mat[MAXN];
punct drlo[MAXM], drhi[MAXM];
char getChar()
{
if (cursor == DIM) {
fread(buf, 1, DIM, stdin);
cursor = 0;
}
return buf[cursor];
}
int readInt()
{
char c;
for (c = getChar(); c != '-' && !(c >= '0' && c <= '9'); c = getChar())
cursor++;
int semn = 1, nr = 0;
if (c == '-') {
semn = -1;
cursor++;
}
for (c = getChar(); c >= '0' && c <= '9'; c = getChar()) {
nr = nr*10 + c-'0';
cursor++;
}
return semn*nr;
}
void citire()
{
n = readInt();
for (int i = 1; i <= n; i++) {
mat[i].x = readInt();
mat[i].y = readInt();
}
m = readInt();
for (int i = 1; i <= m; i++) {
drlo[i].x = readInt();
drlo[i].y = readInt();
drhi[i].x = readInt();
drhi[i].y = readInt();
}
}
vector<int> v;
void normalizare()
{
for (int i = 1; i <= n; i++)
v.push_back(mat[i].x);
for (int i = 1; i <= m; i++) {
v.push_back(drlo[i].x);
v.push_back(drhi[i].x);
}
sort(v.begin(), v.end());
for (int i = 1; i <= n; i++)
mat[i].x = lower_bound(v.begin(), v.end(), mat[i].x) - v.begin();
for (int i = 1; i <= m; i++) {
drlo[i].x = lower_bound(v.begin(), v.end(), drlo[i].x) - v.begin();
drhi[i].x = lower_bound(v.begin(), v.end(), drhi[i].x) - v.begin();
}
v.clear();
for (int i = 1; i <= n; i++)
v.push_back(mat[i].y);
for (int i = 1; i <= m; i++) {
v.push_back(drlo[i].y);
v.push_back(drhi[i].y);
}
sort(v.begin(), v.end());
for (int i = 1; i <= n; i++)
mat[i].y = lower_bound(v.begin(), v.end(), mat[i].y) - v.begin();
for (int i = 1; i <= m; i++) {
drlo[i].y = lower_bound(v.begin(), v.end(), drlo[i].y) - v.begin();
drhi[i].y = lower_bound(v.begin(), v.end(), drhi[i].y) - v.begin();
}
}
bool cmp(punct e, punct f)
{
if (e.x != f.x) return e.x < f.x;
return e.y < f.y;
}
unordered_map<int, unordered_map<int, int> > unm;
inline int zero(int x)
{
return x & (x ^ (x-1));
}
void update(int x, int y, int val)
{
for (int i = x; i < MAX_VAL; i += zero(i))
for (int j = y; j < MAX_VAL; j += zero(j))
unm[i][j] += val;
}
int query(int x, int y)
{
int rez = 0;
for (int i = x; i > 0; i -= zero(i))
for (int j = y; j > 0; j -= zero(j))
rez += unm[i][j];
return rez;
}
void init()
{
MAX_VAL = (n+m)<<1;
int a = 1;
for (int i = 1; i <= n; i++)
update(mat[i].x+a, mat[i].y+a, 1);
}
void solve()
{
int a = 1;
for (int i = 1; i <= m; i++) {
int x0 = drlo[i].x + a;
int y0 = drlo[i].y + a;
int x1 = drhi[i].x + a;
int y1 = drhi[i].y + a;
int rez = query(x1, y1) - query(x1, y0-1) - query(x0-1, y1) + query(x0-1, y0-1);
printf("%d\n", rez);
}
}
int main()
{
freopen("zoo.in", "r", stdin);
freopen("zoo.out", "w", stdout);
fread(buf, 1, DIM, stdin);
citire();
normalizare();
init();
solve();
return 0;
}