Cod sursa(job #2033450)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 6 octombrie 2017 20:14:21
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.96 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define size(x) x[0]

using namespace std;

ifstream cin("zoo.in");
ofstream cout("zoo.out");

class Segment_tree {
public:
  Segment_tree(int n) {
    this -> n = n;
    animal.resize(this -> n + 1);
    
    arb.resize(this -> n << 2);
    for (auto &x : arb) {
      x.resize(this -> n + 1);
    }

    p_init();
  }

  void query(pair < int, int > x_lim, pair < int, int > y_lim) {
    int lower_bound_x = p_get_x_index(x_lim.first, true, 1, this -> n);
    int upper_bound_x = p_get_x_index(x_lim.second, false, 1, this -> n);
    if (lower_bound_x == -1 or upper_bound_x == -1) {
      cout << 0 << '\n';
      return;
    }

    cout << p_query(lower_bound_x, upper_bound_x,
     y_lim.first, y_lim.second, 1, this -> n, 1) << '\n';
  }

private:
  int n;
  vector < vector < int > > arb;
  vector < pair < int, int > > animal;

  void p_init() {
    for (int i = 1; i <= this -> n; i ++) {
      int x, y;
      cin >> x >> y;
      animal[i] = {x, y};
    }

    sort(animal.begin() + 1, animal.end());
    p_fill(1, 1, this -> n);
  }

  void merge(int target, int left, int right) {
    int i = 1; 
    int j = 1;
    int index = 0;
    while (i <= size(arb[left]) and j <= size(arb[right])) {
      if (arb[left][i] <= arb[right][j]) {
        arb[target][++ index] = arb[left][i ++];
      }
      else {
        arb[target][++ index] = arb[right][j ++];
      }
    }

    if (i > size(arb[left])) {
      while (j <= size(arb[right])) {
        arb[target][++ index] = arb[right][j ++];
      }
    }
    else {
      while (i <= size(arb[left])) {
        arb[target][++ index] = arb[left][i ++];
      }
    }

    arb[target][0] = index;
  }

  void p_fill(int nod, int st, int dr) {
    if (st == dr) {
      size(arb[nod]) = 1;
      arb[nod][1] = animal[st].second;
      return;
    }

    int mid = (st + dr) >> 1;
    int left = (nod << 1);
    int right = left + 1;
    p_fill(left, st, mid);
    p_fill(right, mid + 1, dr);
    merge(nod, left, right);
  }

  int p_get_x_index(int x, bool left, int st, int dr) {
    
    int sol = -1;
    while (st <= dr) {
      int cur = (st + dr) >> 1;
      
      if (left) {
        if (animal[cur].first >= x) {
          sol = cur;
          dr = cur - 1;
          continue;
        }
        st = cur + 1;
        continue;
      }

      if (animal[cur].first <= x) {
        sol = cur;
        st = cur + 1;
        continue;
      }
      dr = cur - 1;
    }
    return sol;
  }

  int p_get_y_index(int x, bool left, int st, int dr, int nod) {
    
    int sol = -1;
    while (st <= dr) {
      int cur = (st + dr) >> 1;
      
      if (left) {
        if (arb[nod][cur] >= x) {
          sol = cur;
          dr = cur - 1;
          continue;
        }
        st = cur + 1;
        continue;
      }

      if (arb[nod][cur] <= x) {
        sol = cur;
        st = cur + 1;
        continue;
      }
      dr = cur - 1;
    }
    return sol;
  }


  int p_query(int lower_bound_x, int upper_bound_x, int lower_bound_y,
   int upper_bound_y, int st, int dr, int nod) {

    if (st >= lower_bound_x and dr <= upper_bound_x) {
      int l = p_get_y_index(lower_bound_y, true, st, dr, nod);
      int r = p_get_y_index(upper_bound_y, false, st, dr, nod);
      if (r == -1 or l == -1) {
        return 0;
      }

      return r - l + 1;
    }

    int mid = (st + dr) >> 1;
    int left = (nod << 1);
    int right = left + 1;
    int l = 0, r = 0;

    if (lower_bound_x <= mid) {
      l = p_query(lower_bound_x, upper_bound_x,
       lower_bound_y, upper_bound_y, st, mid, left);
    }
    if (upper_bound_x >= mid + 1) {
      r = p_query(lower_bound_x, upper_bound_x,
       lower_bound_y, upper_bound_y, mid + 1, dr, right);
    }

    return l + r;
  }
};

int main(int argc, char const *argv[]) {
  
  int n;
  cin >> n;
  Segment_tree *T = new Segment_tree(n);

  int m;
  cin >> m;
  for (int i = 1; i <= m; i ++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    T -> query({x1, x2}, {y1, y2});
  }
}