Cod sursa(job #2762186)

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

using namespace std;

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

struct SegTree {
  int Size;
  vector<vector<int>> tree;

  SegTree(int n) {
    Size = 1;
    while (Size < n)
      Size <<= 1;
    tree.resize(Size << 1);
  }

  void update(int x, int lx, int rx, int poz, int val) {
    if (lx == rx) {
      tree[x].emplace_back(val);
      return;
    }
    int mid = (lx + rx) >> 1;
    if (poz <= mid)
      update(x << 1, lx, mid, poz, val);
    else update(x << 1 | 1, mid + 1, rx, poz, val);
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      sort(tree[x].begin(), tree[x].end());
      return;
    }
    int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
    build(lSon, lx, mid);
    build(rSon, mid + 1, rx);
    tree[x].resize(tree[lSon].size() + tree[rSon].size());
    merge(tree[lSon].begin(), tree[lSon].end(), tree[rSon].begin(), tree[rSon].end(), tree[x].begin());
  }

  int query(int x, int lx, int rx, int x1, int x2, int y1, int y2) {
    if (x1 <= lx && rx <= x2)
      return upper_bound(tree[x].begin(), tree[x].end(), y2) - lower_bound(tree[x].begin(), tree[x].end(), y1);
    int mid = (lx + rx) >> 1, ans1 = 0, ans2 = 0;
    if (x1 <= mid)
      ans1 = query(x << 1, lx, mid, x1, x2, y1, y2);
    if (mid < x2)
      ans2 = query(x << 1 | 1, mid + 1, rx, x1, x2, y1, y2);
    return ans1 + ans2;
  }
};

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

vector<int> X;

struct point {
  int x, y;

  void read() {
    fin >> x >> y;
    X.emplace_back(x);
  }
} v[1 + MAXN];

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

  void read() {
    fin >> x1 >> y1 >> x2 >> y2;
    X.emplace_back(x1);
    X.emplace_back(x2);
  }
} q[1 + MAXM];

int N;

int main() {
  int n;
  fin >> n;
  for (int i = 1; i <= n; ++i)
    v[i].read();
  int m;
  fin >> m;
  for (int i = 1; i <= m; ++i)
    q[i].read();
  sort(X.begin(), X.end());
  map<int,int> val;
  val[X.front()] = ++N;
  for (size_t i = 1; i < X.size(); ++i)
    if (X[i] != X[i - 1])
      val[X[i]] = ++N;
  SegTree tree(N);
  for (int i = 1; i <= n; ++i) {
    v[i].x = val[v[i].x];
    tree.update(1, 1, N, v[i].x, v[i].y);
  }
  tree.build(1, 1, N);
  for (int i = 1; i <= m; ++i) {
    q[i].x1 = val[q[i].x1];
    q[i].x2 = val[q[i].x2];
    fout << tree.query(1, 1, N, q[i].x1, q[i].x2, q[i].y1, q[i].y2) << '\n';
  }
  fin.close();
  fout.close();
  return 0;
}