Cod sursa(job #3307609)

Utilizator n6v26rDedu Razvan Matei n6v26r Data 22 august 2025 03:53:31
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.19 kb
// 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 { CLOSE, OPEN } 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 == 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 (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;
}