Cod sursa(job #2762183)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 5 iulie 2021 23:07:24
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

const int MAXN = 16000;
const int MAXM = 1e5;

struct point {
  int x, y;

  void read() {
    fin >> x >> y;
  }

  bool operator < (const point &A) const {
    if (x != A.x)
      return x < A.x;
    return y < A.y;
  }
} v[1 + MAXN];

struct query {
  int x1, y1, x2, y2, index;

  void read() {
    fin >> x1 >> y1 >> x2 >> y2;
  }

  bool operator < (const query &A) const {
    if (x1 != A.x1)
      return x1 < A.x1;
    if (x2 != A.x2)
      return x2 < A.x2;
    if (y1 != A.y1)
      return y1 < A.y1;
    return y2 < A.y2;
  }
} q[1 + MAXM];

int N, aib[1 + MAXN + 2 * MAXM], sol[1 + MAXM];

void update(int x, int t) {
  for (int i = x; i <= N; i += i & -i)
    aib[i] += t;
}

int query(int l, int r) {
  int ans = 0;
  for (int i = r; i > 0; i -= i & -i)
    ans += aib[i];
  for (int i = l - 1; i > 0; i -= i & -i)
    ans -= aib[i];
  return ans;
}

int main() {
  int n;
  fin >> n;
  vector<int> Y;
  for (int i = 1; i <= n; ++i) {
    v[i].read();
    Y.emplace_back(v[i].y);
  }
  sort(v + 1, v + n + 1);
  int m;
  fin >> m;
  for (int i = 1; i <= m; ++i) {
    q[i].read();
    q[i].index = i;
    Y.emplace_back(q[i].y1);
    Y.emplace_back(q[i].y2);
  }
  sort(q + 1, q + m + 1);
  sort(Y.begin(), Y.end());
  unordered_map<int,int> val;
  val[Y.front()] = ++N;
  for (size_t i = 1; i < Y.size(); ++i)
    if (Y[i] != Y[i - 1])
      val[Y[i]] = ++N;
  for (int i = 1; i <= n; ++i)
    v[i].y = val[v[i].y];
  for (int i = 1; i <= m; ++i) {
    q[i].y1 = val[q[i].y1];
    q[i].y2 = val[q[i].y2];
  }
  val.clear();
  int p1 = 1, p2 = 1;
  for (int i = 1; i <= m; ++i) {
    while (p2 <= n && v[p2].x <= q[i].x2) {
      update(v[p2].y, 1);
      ++p2;
    }
    while (p1 <= n && v[p1].x < q[i].x1) {
      update(v[p1].y, -1);
      ++p1;
    }
    sol[q[i].index] = query(q[i].y1, q[i].y2);
  }
  for (int i = 1; i <= m; ++i)
    fout << sol[i] << '\n';
  fin.close();
  fout.close();
  return 0;
}