Cod sursa(job #2762188)

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

using namespace std;

struct InParser {
  FILE * fin;
  char * buff;
  int sp;

  char read_ch() {
    ++sp;
    if (sp == 4096) {
      sp = 0;
      fread(buff, 1, 4096, fin);
    }
    return buff[sp];
  }

  InParser(const char * nume) {
    fin = fopen(nume, "r");
    buff = new char[4096]();
    sp = 4095;
  }

  InParser & operator >> (int & n) {
    char c;
    while (!isdigit(c = read_ch()) && c != '-');
    int sgn = 1;
    if (c == '-') {
      n = 0;
      sgn = -1;
    } else {
      n = c - '0';
    }
    while (isdigit(c = read_ch())) {
      n = 10 * n + c - '0';
    }
    n *= sgn;
    return *this;
  }
};

struct OutParser {
  FILE * fout;
  char * buff;
  int sp;

  void write_ch(char ch) {
    if (sp == 50000) {
      fwrite(buff, 1, 50000, fout);
      sp = 0;
      buff[sp++] = ch;
    } else {
      buff[sp++] = ch;
    }
  }

  OutParser(const char * name) {
    fout = fopen(name, "w");
    buff = new char[50000]();
    sp = 0;
  }

  ~OutParser() {
    fwrite(buff, 1, sp, fout);
    fclose(fout);
  }

  OutParser & operator << (int vu32) {
    if (vu32 <= 9) {
      write_ch(vu32 + '0');
    } else {
      ( * this) << (vu32 / 10);
      write_ch(vu32 % 10 + '0');
    }
    return *this;
  }

  OutParser & operator << (char ch) {
    write_ch(ch);
    return *this;
  }

  OutParser & operator << (const char * ch) {
    while ( * ch) {
      write_ch( * ch);
      ++ch;
    }
    return *this;
  }
};

InParser fin("zoo.in");
OutParser 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());
  unordered_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';
  }
  return 0;
}