Cod sursa(job #2761774)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 3 iulie 2021 22:32:35
Problema Zoo Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#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;
    }
  }
}

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);

    top_x = norm_x[*std::lower_bound(vec_x.begin(), vec_x.end() - 1, top_x)];
    top_y = norm_y[*std::lower_bound(vec_y.begin(), vec_y.end() - 1, top_y)];

    bot_x = norm_x[*std::lower_bound(vec_x.begin(), vec_x.end() - 1, bot_x)];
    bot_y = norm_y[*std::lower_bound(vec_y.begin(), vec_y.end() - 1, 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;

      auto left = std::lower_bound(norm_points_y[x].begin(), norm_points_y[x].end() - 1, top_y);
      auto right = std::lower_bound(norm_points_y[x].begin(), norm_points_y[x].end() - 1, 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;
}