Cod sursa(job #2761937)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 4 iulie 2021 15:21:48
Problema Zoo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.79 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;
int mx_x = -1;

std::vector<int> vec_y;
std::unordered_map<int, int> norm_y;
int mx_y = -1;

std::vector<std::pair<int, int>> points;
std::vector<int> norm_points_y[1 + 2 * NMAX];

std::vector<int> seg_tree[4 * 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;
}

void merge(const std::vector<int>& a, const std::vector<int>& b, std::vector<int>& target) {
  target.reserve(a.size() + b.size());

  int i = 0, j = 0;

  while (i < a.size() && j < b.size()) {
    if (a[i] < b[j]) {
      target.push_back(a[i]);
      ++i;
    }
    else {
      target.push_back(a[j]);
      ++j;
    }
  }

  while (i < a.size()) {
    target.push_back(a[i]);
    ++i;
  }

  while (j < b.size()) {
    target.push_back(b[j]);
    ++j;
  }
}

void build_seg_tree(int seg_tree_index, int left, int right) {
  if (left == right) {
    seg_tree[seg_tree_index] = std::vector<int>(norm_points_y[left]);
    return;
  }

  int left_child_index = 2 * seg_tree_index;
  int right_child_index = 2 * seg_tree_index + 1;
  int mid = (left + right) / 2;

  build_seg_tree(left_child_index, left, mid);
  build_seg_tree(right_child_index, mid + 1, right);

  merge(seg_tree[left_child_index], seg_tree[right_child_index], seg_tree[seg_tree_index]);
}

int cnt_points(int seg_tree_index, int top_y, int bot_y) {
  if (seg_tree[seg_tree_index].empty())
    return 0;

  if (top_y > seg_tree[seg_tree_index].back() || bot_y < seg_tree[seg_tree_index].front())
    return 0;

  auto left = bs_greater_equal(seg_tree[seg_tree_index], top_y);
  auto right = bs_less_equal(seg_tree[seg_tree_index], bot_y);

  return right - left + 1;
}

int query_seg_tree(int seg_tree_index, int left, int right, int top_x, int bot_x, int top_y, int bot_y) {
//  std::printf("query on the seg_tree at index %d (left = %d, right = %d) top_x = %d, bot_x = %d, top_y = %d, bot_y = %d\n", seg_tree_index, left, right, top_x, bot_x, top_y, bot_y);
  if (top_x <= left && right <= bot_x)
    return cnt_points(seg_tree_index, top_y, bot_y);

  if (left > bot_x || right < top_x)
    return 0;

  int left_child_index = 2 * seg_tree_index;
  int right_child_index = 2 * seg_tree_index + 1;
  int mid = (left + right) / 2;

  return query_seg_tree(left_child_index, left, mid, top_x, bot_x, top_y, bot_y)
  + query_seg_tree(right_child_index, mid + 1, right, top_x, bot_x, top_y, bot_y);
}


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);
  mx_x = norm_x[vec_x.back()];

  normalise(vec_y, norm_y);
  mx_y = norm_y[vec_y.back()];

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

  build_seg_tree(1, 0, mx_x);

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

    out << query_seg_tree(1, 0, mx_x, top_x, bot_x, top_y, bot_y) << '\n';
  }

  return 0;
}