Cod sursa(job #1680709)

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

#define pb push_back
#define pi pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define bins lower_bound

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];
pi pts[N];
vector<int> xC, yC;

inline int xNorm(int x) {
   return upper_bound(xC.begin(), xC.end(), x) - xC.begin() + 1;
}

inline int yNorm(int y) {
   return upper_bound(yC.begin(), yC.end(), y) - yC.begin() + 1;
}

inline int xInd(int indx) {
   if(indx > xC.size()) indx = xC.size();
   if(indx < 0) indx = 0;
   return indx;
}

inline int yInd(int indx) {
   if(indx > yC.size()) indx = yC.size();
   if(indx < 0) indx = 0;
   return indx;
}

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

   in >> n;
   for(i = 1; i <= n; i++) {
      in >> x1 >> y1;
      xC.pb(x1);
      yC.pb(y1);
      pts[i] = mp(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, yNorm(pts[i].se));
   }

   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();
      /*X1 = xInd(xNorm(x1) - 1);
      X2 = xInd(xNorm(x2));
      Y1 = yInd(yNorm(y1));
      Y2 = yInd(yNorm(y2));

      out << x1 << ' ' << X1 << '\n';
      out << x2 << ' ' << X2 << '\n';
      out << y1 << ' ' << Y1 << '\n';
      out << y2 << ' ' << Y2 << '\n';
      out << "------------\n";*/

      out << query(r[X2], 1, n, Y1, Y2) - query(r[X1], 1, n, Y1, Y2) << '\n';
   }

   return 0;
}