Cod sursa(job #2815683)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 10 decembrie 2021 08:31:32
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <fstream>
#include <vector>
#include <algorithm>

const int N = 16000;

std::pair<int, int> points[N + 1];

std::vector<int> segment_tree[N * 4 + 1];
std::vector<int> list[N + 1];

void build(int node, int left, int right)
{
  if (left == right) {
    std::swap(segment_tree[node], list[left]);
    std::sort(std::begin(segment_tree[node]),
              std::end(segment_tree[node]));
  } else {
    int middle = (left + right) / 2;

    build(node * 2, left, middle);
    build(node * 2 + 1, middle + 1, right);

    std::merge(
        std::begin(segment_tree[node * 2]), 
        std::end(segment_tree[node * 2]),
        std::begin(segment_tree[node * 2 + 1]), 
        std::end(segment_tree[node * 2 + 1]),
        std::back_inserter(segment_tree[node]));
  }
}

int query(int node, int left, int right, 
          int x_left, int x_right, int y_left, int y_right)
{
  if (x_left <= left and right <= x_right) {
    return std::upper_bound(
              std::begin(segment_tree[node]), 
              std::end(segment_tree[node]), y_right) -
           std::lower_bound(
              std::begin(segment_tree[node]), 
              std::end(segment_tree[node]), y_left);
  } else {
    int middle = (left + right) / 2;

    if (x_right <= middle)
      return query(node * 2, left, middle, 
                   x_left, x_right, y_left, y_right);
    if (middle + 1 <= x_left)
      return query(node * 2 + 1, middle + 1, right,
                   x_left, x_right, y_left, y_right);

    int answer_left = query(node * 2, left, middle, 
                            x_left, x_right, y_left, y_right),
        answer_right = query(node * 2 + 1, middle + 1, right,
                             x_left, x_right, y_left, y_right);

    return answer_left + answer_right;
  }
}

int main(void)
{
  std::ifstream in("zoo.in");
  std::ofstream out("zoo.out");
  
  int n; 
  in >> n;

  std::vector<int> coordX;
  for (int i = 1; i <= n; ++i) {
    in >> points[i].first >> points[i].second;
    coordX.push_back(points[i].first);
  }

  std::sort(std::begin(coordX), std::end(coordX));
  coordX.resize(std::unique(std::begin(coordX), std::end(coordX)) - 
                std::begin(coordX));

  for (int i = 1; i <= n; ++i) {
    points[i].first = std::lower_bound(
                          std::begin(coordX), std::end(coordX), points[i].first) -
                      std::begin(coordX) + 1;
    list[points[i].first].push_back(points[i].second);
  }
  build(1, 1, static_cast<int>(coordX.size()));

  int q;
  in >> q;
  while (q--) {
    int x_left, y_left, x_right, y_right;
    in >> x_left >> y_left >> x_right >> y_right;

    x_left = std::lower_bound(
                std::begin(coordX), std::end(coordX), x_left) -
             std::begin(coordX) + 1;
    x_right = std::upper_bound(
                  std::begin(coordX), std::end(coordX), x_right) -
              std::begin(coordX);

    out << query(1, 1, static_cast<int>(coordX.size()),
                 x_left, x_right, y_left, y_right) << "\n";
  }

  return 0;
}