Pagini recente » Cod sursa (job #1172009) | Cod sursa (job #2768293) | Cod sursa (job #2339355) | Cod sursa (job #2322191) | Cod sursa (job #2761775)
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
const int NMAX = 16e3;
int n;
std::vector<int> vec_x;
std::unordered_map<int, int> norm_x;
std::vector<int> vec_y;
std::unordered_map<int, int> norm_y;
std::vector<std::pair<int, int>> points;
std::vector<int> norm_points_y[1 + 2 * NMAX];
void normalise(std::vector<int>& coords, std::unordered_map<int, int>& target) {
std::sort(coords.begin(), coords.end());
int value = -1;
for (auto &coord: coords) {
if (target.find(coord) == target.end()) {
++value;
target[coord] = value;
}
}
}
// first element greater or equal to val
// -1 if it's greater than the last element
int bs_greater_equal(std::vector<int>& a, int val) {
int left = 0, right = a.size() - 1, ans = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] >= val) {
ans = mid;
right = mid - 1;
}
else
left = mid + 1;
}
return ans;
}
// last element less or equal to val
// -1 if it's the smallest element
int bs_less_equal(const std::vector<int>& a, int val) {
int left = 0, right = a.size() - 1, ans = -1;
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] <= val) {
ans = mid;
left = mid + 1;
} else
right = mid - 1;
}
return ans;
}
int main() {
std::ifstream in("zoo.in");
std::ofstream out("zoo.out");
in >> n;
for (int i = 1; i <= n; ++i) {
int x, y;
in >> x >> y;
points.emplace_back(x, y);
vec_x.push_back(x);
vec_y.push_back(y);
}
normalise(vec_x, norm_x);
normalise(vec_y, norm_y);
for (auto& point: points)
norm_points_y[norm_x[point.first]].push_back(norm_y[point.second]);
for (auto& vec: norm_points_y)
std::sort(vec.begin(), vec.end());
int queries;
in >> queries;
while (queries--) {
int top_x, top_y, bot_x, bot_y;
in >> top_x >> top_y >> bot_x >> bot_y;
// std::printf("query with top_x = %d, top_y = %d, bot_x = %d, bot_y = %d\n", top_x, top_y, bot_x, bot_y);
if (top_x > vec_x.back() || top_y > vec_y.back() || bot_x < vec_x.front() || bot_y < vec_y.front()) {
out << "0\n";
continue;
}
top_x = norm_x[vec_x[bs_greater_equal(vec_x, top_x)]];
top_y = norm_y[vec_y[bs_greater_equal(vec_y, top_y)]];
bot_x = norm_x[vec_x[bs_less_equal(vec_x, bot_x)]];
bot_y = norm_y[vec_y[bs_less_equal(vec_y, bot_y)]];
// std::printf("normalised query with top_x = %d, top_y = %d, bot_x = %d, bot_y = %d\n", top_x, top_y, bot_x, bot_y);
int ans = 0;
for (int x = top_x; x <= bot_x; ++x) {
if (norm_points_y[x].empty())
continue;
if (top_y > norm_points_y[x].back() || bot_y < norm_points_y[x].front())
continue;
auto left = bs_greater_equal(norm_points_y[x], top_y);
auto right = bs_less_equal(norm_points_y[x], bot_y);
ans += right - left + 1;
// std::printf("adding %d for x = %d\n", right - left, x);
// std::cout << "points were: ";
// for (auto& y : norm_points_y[x])
// std::cout << y << " ";
// std::cout << '\n';
}
out << ans << '\n';
}
return 0;
}