Cod sursa(job #1680716)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 8 aprilie 2016 23:57:35
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 16005;

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

struct Node {
   int sum;
   Node *ls, *rs;

   Node() {
      sum = 0;
      ls = rs = nullptr;
   }
};

void build(Node *cur, int l, int r) {
   if(l == r) return;

   cur->ls = new Node();
   cur->rs = new Node();

   int med = (l + r) >> 1;
   build(cur->ls, l, med);
   build(cur->rs, med + 1, r);
}

void update(Node *cur, Node *prev, int l, int r, int pos) {
   if(l == r) {
      cur->sum = prev->sum + 1;
      return;
   }

   int med = (l + r) >> 1;
   if(pos <= med) {
      cur->ls = new Node();
      update(cur->ls, prev->ls, l, med, pos);
      cur->rs = prev->rs;
   }
   else {
      cur->rs = new Node();
      update(cur->rs, prev->rs, med + 1, r, pos);
      cur->ls = prev->ls;
   }
   cur->sum = cur->ls->sum + cur->rs->sum;
}

int query(Node *cur, int l, int r, int i, int j) {
   if(i <= l && r <= j) return cur->sum;

   int qans = 0, med = (l + r) >> 1;
   if(i <= med) qans += query(cur->ls, l, med, i, j);
   if(med < j) qans += query(cur->rs, med + 1, r, i, j);
   return qans;
}

int n, m;
Node *r[N];
pair<int, int> pts[N];
vector<int> xC, yC;

int main() {
   int i, x1, y1, x2, y2;

   in >> n;
   for(i = 1; i <= n; i++) {
      in >> x1 >> y1;
      xC.push_back(x1);
      yC.push_back(y1);
      pts[i] = make_pair(x1, y1);
   }

   r[0] = new Node();
   build(r[0], 1, n);

   sort(pts + 1, pts + n + 1);
   sort(xC.begin(), xC.end());
   sort(yC.begin(), yC.end());

   for(i = 1; i <= n; i++) {
      r[i] = new Node();
      update(r[i], r[i - 1], 1, n, upper_bound(yC.begin(), yC.end(), pts[i].second) - yC.begin());
   }

   in >> m;
   for(i = 1; i <= m; i++) {
      in >> x1 >> y1 >> x2 >> y2;

      int X1, Y1, X2, Y2;

      X1 = lower_bound(xC.begin(), xC.end(), x1) - xC.begin();
      X2 = upper_bound(xC.begin(), xC.end(), x2) - xC.begin();
      Y1 = lower_bound(yC.begin(), yC.end(), y1) - yC.begin() + 1;
      Y2 = upper_bound(yC.begin(), yC.end(), y2) - yC.begin();

      if(Y1 > Y2 || X1 > X2) {
         out << "0\n";
      }
      else {
         out << query(r[X2], 1, n, Y1, Y2) - query(r[X1], 1, n, Y1, Y2) << '\n';
      }
   }

   return 0;
}