Pagini recente » Cod sursa (job #2280620) | Cod sursa (job #2432365) | Cod sursa (job #283136) | Cod sursa (job #8487) | Cod sursa (job #2431826)
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
const int NMax = 16000;
vector <int> AIT[4 * NMax + 5]; pair <int, int> V[NMax + 5];
int N, M, x1, x2, y1, y2;
void Build(int i, int st, int dr)
{
if(st == dr)
{
AIT[i].push_back(V[st].second);
return;
}
int m = (st + dr) >> 1;
Build(2 * i, st, m);
Build(2 * i + 1, m + 1, dr);
for(auto a : AIT[2 * i])
AIT[i].push_back(a);
for(auto a : AIT[2 * i + 1])
AIT[i].push_back(a);
sort(AIT[i].begin(), AIT[i].end());
}
int Querry(int i, int st, int dr)
{
int a = V[st].first, b = V[dr].first, m = (st + dr) >> 1;
if(x2 < a || b < x1)
return 0;
if(x1 <= a && b <= x2)
{
return upper_bound(AIT[i].begin(), AIT[i].end(), y2) -
lower_bound(AIT[i].begin(), AIT[i].end(), y1);
}
return (Querry(2 * i, st, m) + Querry(2 * i + 1, m + 1, dr));
}
int main()
{
fin >> N;
for(int i = 1, a, b; i <= N; i++)
fin >> a >> b, V[i] = {a, b};
sort(V + 1, V + N + 1);
Build(1, 1, N); fin >> M;
while(M--)
{
fin >> x1 >> y1 >> x2 >> y2;
fout << Querry(1, 1, N) << '\n';
}
fin.close();
fout.close();
return 0;
}