Cod sursa(job #3307613)

Utilizator n6v26rDedu Razvan Matei n6v26r Data 22 august 2025 04:57:08
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.4 kb
/*                                ___   __   __                                   */
/*                               [_  | /  \ /  \                                  */
/*                                / /_| () | () |                                 */
/*                              _|____]\__/ \__/_                                 */
/*                          _.-"|   |   |   |   |"-._                             */
/*                      _.-"|   |   |   |   |   |   |"-._                         */
/*                  _.-"|   |   |   |   |   |   |   |   |"-._                     */
/*             _.-"`|   |   |   |   |   |   |   |   |   |   |`"-._                */
/*         _.-" |   |   | __|.-~|~-.|   |_..|.__|   |   |   |   | "-._            */
/*        " |   |   |   |'  | ` |  \|~"~|   |   |`-.|   |   |   |   | "           */
/*          |   |   |  /| _ |   |)  |\  |   |   |   |\  |   |   |   |             */
/*          |   |   | /`| a)|   |   | | |   |   |   | `\|   |   |   |             */
/*          |   |   |:` |   |  /|   | | |   |   |   |   |   |   |   |             */
/*          |   |`-.||` |.-.| ( |   |/  |.  |   |   | `;|\  |   |   |             */
/*          |   |`-.|`--|_.'|.;\|__/|   |   |  .|   |  ||\\ |   |   |             */
/*          | _ |   |:--|   | | |   |  /|   |/  |   | .'| \\|   |   |             */
/*          |("\|  /|/  |   | | |   | ' |   |   |   | / |  :|;  |   |             */
/*          |`\'|_/`|   |   | .\|   |/`~|=-.|   |   |/  |  `|   |   |             */
/*          |  `|_.'|   |   | /`|   ||  |   |\  |   |(  |   |   |   |             */
/*          |   |   |   |   |/  |\  ||  |   | `Y|  /| \ |   |   |   |             */
/*          |   |   |   |   |  /| Y ||  |   |  || /`|  \|   |   |   |             */
/*          |   |   |   |  /| | | | ||  |   |  || | ||  |   |   |   |             */
/*          |   |   |   | "-|-" |/__||  |   | /_|_| |/__|   |   |   |             */
/*          |   |   |   |   |   |'""|   |   | '"|"  |"""|   |   |   |             */
/*        __|___|___|___|___|___|___|___|___|___|___|___|___|___|___|__           */
// NAME: zoo
// SOURCE: .compion 2003
// URL: https://www.infoarena.ro/problema/zoo
// Normalize points, and do a vertical scanline + BIT
#include <algorithm>
#include <stdio.h>

#include <utility>
#include <vector>

#define MAXN 16'001
#define MAXM 100'001

struct Point {
  int x;
  int y;
} animale[MAXN];

struct dreptunghi {
  int i;
  int j;
  int l;
  int c;
} submat[MAXM];

std::vector<std::pair<int, int>> norm;

struct Query {
  enum OP { OPEN = 0, CLOSE = 1 } op;
  int id;
};

struct Event {
  enum TYPE { POINT = 0, DREPT = 1 } type;

  int y;

  union {
    int x;
    Query query;
  };
};

std::vector<Event> ev;
int ans[MAXM];

int n, m;

struct Fenwick {
  int aib[MAXN + 1];

  void update(int pos, int val) {
    pos++; // indexed starting with 1
    while (pos <= n) {
      aib[pos] += val;
      pos += (pos & (-pos));
    }
  }

  int query(int pos) {
    if (pos < 0)
      return 0;
    pos++;
    int sum = 0;
    while (pos) {
      sum += aib[pos];
      pos -= (pos & (-pos));
    }
    return sum;
  }

  int query(int st, int dr) { return query(dr) - query(st - 1); }
};

Fenwick aib;

int cautbinLower(int pos) {
  int s = -1;
  int d = norm.size() - 1;
  while (d - s > 1) {
    int m = (s + d) / 2;
    if (norm[m].first < pos)
      s = m;
    else
      d = m;
  }

  if (norm[d].first < pos)
    return -1;

  return norm[d].second;
}

int cautbinUpper(int pos) {
  int s = -1;
  int d = norm.size();
  while (d - s > 1) {
    int m = (s + d) / 2;
    if (norm[m].first > pos)
      d = m;
    else
      s = m;
  }

  if (s == -1)
    return -1;

  return norm[s].second;
}

int main() {
  freopen("zoo.in", "r", stdin);
  freopen("zoo.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &animale[i].y, &animale[i].x);
  }
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d%d", &submat[i].i, &submat[i].j, &submat[i].l, &submat[i].c);
  }

  std::sort(animale, animale + n, [](Point &a, Point &b) { return a.x < b.x; });
  for (int i = 0; i < n; i++) {
    norm.push_back(std::make_pair(animale[i].x, i));
    ev.push_back({.type = Event::TYPE::POINT, .y = animale[i].y, .x = i});
  }

  for (int i = 0; i < m; i++) {
    ev.push_back({.type = Event::TYPE::DREPT,
                  .y = submat[i].i,
                  .query = {.op = Query::OP::OPEN, .id = i}});
    ev.push_back({.type = Event::TYPE::DREPT,
                  .y = submat[i].l,
                  .query = {.op = Query::OP::CLOSE, .id = i}});
  }

  std::sort(ev.begin(), ev.end(), [](Event &a, Event &b) -> bool {
    if (a.y != b.y)
      return a.y < b.y;

    if (a.type == b.type) {
      return a.query.op < b.query.op;
    }

    if ((a.type == Event::TYPE::DREPT && a.query.op == Query::CLOSE) ||
        (b.type == Event::TYPE::DREPT && b.query.op == Query::CLOSE))
      return a.type < b.type;
    else
      return a.type > b.type;
  });

  for (auto e : ev) {
    if (e.type == Event::TYPE::POINT) {
      aib.update(e.x, 1);
    } else {
      int x1 = cautbinLower(submat[e.query.id].j);
      int x2 = cautbinUpper(submat[e.query.id].c);
      if (x1 > x2 || x1 == -1 || x2 == -1)
        continue;
      if (e.query.op == Query::OP::OPEN)
        ans[e.query.id] -= aib.query(x1, x2);
      else
        ans[e.query.id] += aib.query(x1, x2);
    }
  }

  for (int i = 0; i < m; i++) {
    printf("%d\n", ans[i]);
  }

  return 0;
}