Cod sursa(job #1900530)

Utilizator BrandonChris Luntraru Brandon Data 3 martie 2017 14:17:14
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.53 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int MaxN = 16005, MaxM = 100005, rgLim = (1 << 14), Inf = 2000000005;

int n, m, xTop, yTop;

class AnimalType {
public:
  int x, y, normX;

  AnimalType(int _x = 0, int _y = 0, int _normX = 0) {
    x = _x;
    y = _y;
    normX = _normX;
  }
};

AnimalType animal[MaxN];

class SegTreeType {
private:
  int val;
  SegTreeType* lfSon;
  SegTreeType* rgSon;

public:
  SegTreeType(int _val = 0, SegTreeType* _lfSon = nullptr, SegTreeType* _rgSon = nullptr) {
    val = _val;
    lfSon = _lfSon;
    rgSon = _rgSon;
  }

  void buildNode() {
    val = 0;

    if (lfSon != nullptr) {
      val += lfSon->val;
    }

    if (rgSon != nullptr) {
      val += rgSon->val;
    }
  }

  void update(SegTreeType* prvTreeNode, int pos, int lf = 1, int rg = rgLim) {
    if (lf == rg) {
      // ++val;
      return;
    }

    int med = (lf + rg) / 2;

    if (pos <= med) {
      // lfSon = new SegTreeType;

      // if (prvTreeNode != nullptr and rgSon == nullptr) {
      //   rgSon = prvTreeNode->rgSon;
      // }

      if (lfSon == nullptr and (prvTreeNode == nullptr or prvTreeNode->lfSon == nullptr)) {
        lfSon = new SegTreeType(1);
      }
      else if (lfSon == nullptr and prvTreeNode != nullptr and prvTreeNode->lfSon != nullptr) {
        lfSon = new SegTreeType(prvTreeNode->lfSon->val + 1, prvTreeNode->lfSon->lfSon, prvTreeNode->lfSon->rgSon);
      }
      else if (lfSon != nullptr) {
        lfSon = new SegTreeType(lfSon->val + 1, lfSon->lfSon, lfSon->rgSon);
      }

      if (prvTreeNode != nullptr) {
        lfSon->update(prvTreeNode->lfSon, pos, lf, med);
      }
      else {
        lfSon->update(nullptr, pos, lf, med);
      }
    }
    else {
      // rgSon = new SegTreeType;

      // if (prvTreeNode != nullptr and lfSon == nullptr) {
      //   lfSon = prvTreeNode->lfSon;
      // }

      // if (rgSon == nullptr) {
      //   rgSon = new SegTreeType;
      // }

      if (rgSon == nullptr and (prvTreeNode == nullptr or prvTreeNode->rgSon == nullptr)) {
        rgSon = new SegTreeType(1);
      }
      else if (rgSon == nullptr and prvTreeNode != nullptr and prvTreeNode->rgSon != nullptr) {
        rgSon = new SegTreeType(prvTreeNode->rgSon->val + 1, prvTreeNode->rgSon->lfSon, prvTreeNode->rgSon->rgSon);
      }
      else if (rgSon != nullptr) {
        rgSon = new SegTreeType(rgSon->val + 1, rgSon->lfSon, rgSon->rgSon);
      }

      if (prvTreeNode != nullptr) {
        rgSon->update(prvTreeNode->rgSon, pos, med + 1, rg);
      }
      else {
        rgSon->update(nullptr, pos, med + 1, rg);
      }
    }

    if (rgSon == nullptr and prvTreeNode != nullptr) {
      rgSon = prvTreeNode->rgSon;
    }

    if (lfSon == nullptr and prvTreeNode != nullptr) {
      lfSon = prvTreeNode->lfSon;
    }

    buildNode();
  }

  int query(int lfQry, int rgQry, int lf = 1, int rg = rgLim) {
    if (rg < lfQry or lf > rgQry) {
      return 0;
    }

    if (lfQry <= lf and rgQry >= rg) {
      return val;
    }

    int med = (lf + rg) / 2;

    int ansLf = 0;
    if (lfSon != nullptr) {
      ansLf = lfSon->query(lfQry, rgQry, lf, med);
    }

    int ansRg = 0;
    if (rgSon != nullptr) {
      ansRg = rgSon->query(lfQry, rgQry, med + 1, rg);
    }

    return ansLf + ansRg;
  }
};

SegTreeType* RootAtTime[MaxN];

class CoordListType {
public:
  int val, pos;

  CoordListType(int _val = 0, int _pos = 0) {
    val = _val;
    pos = _pos;
  }
};

vector <CoordListType> yList = {-Inf};

inline bool cmpX_animal(const AnimalType& a, const AnimalType& b) {
  if (a.x == b.x) {
    return a.y < b.y;
  }

  return a.x < b.x;
}

inline bool cmpY_animal(const AnimalType& a, const AnimalType& b) {
  if (a.y == b.y) {
    return a.x < b.x;
  }

  return a.y < b.y;
}

int FindLo(int val, bool isTime, int lf = 1, int rg = n) {
  if (isTime) {
    rg = yList.size() - 1;
  }

  int ans = 0;
  while (lf <= rg) {
    int med = (lf + rg) / 2;
    int compValue = (isTime) ? yList[med].val : animal[med].x;
    int candidateAns = (isTime) ? yList[med].pos : med + 1;

    if (compValue < val) {
      lf = med + 1;
      ans = candidateAns;
    }
    else {
      rg = med - 1;
    }
  }

  return ans;
}

int FindHi(int val, bool isTime, int lf = 1, int rg = n) {
  if (isTime) {
    rg = yList.size() - 1;
  }

  int ans = 0;
  while (lf <= rg) {
    int med = (lf + rg) / 2;
    int compValue = (isTime) ? yList[med].val : animal[med].x;
    int candidateAns = (isTime) ? yList[med].pos : med;

    if (compValue <= val) {
      lf = med + 1;
      ans = candidateAns;
    }
    else {
      rg = med - 1;
    }
  }

  return ans;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> animal[i].x >> animal[i].y;
  }

  sort(&animal[1], &animal[n + 1], cmpX_animal);
  animal[1].normX = ++xTop;
  for (int i = 2; i <= n; ++i) {
    if (animal[i].x != animal[i - 1].x) {
      ++xTop;
    }

    animal[i].normX = xTop;
  }

  sort(&animal[1], &animal[n + 1], cmpY_animal);
  ++yTop;
  RootAtTime[yTop] = new SegTreeType;
  RootAtTime[yTop]->update(RootAtTime[yTop - 1], animal[1].normX);
  for (int i = 2; i <= n; ++i) {
    if (animal[i].y != animal[i - 1].y) {
      ++yTop;
      RootAtTime[yTop] = new SegTreeType;
    }

    RootAtTime[yTop]->update(RootAtTime[yTop - 1], animal[i].normX);
    yList.push_back(CoordListType(animal[i].y, yTop));
  }

  sort(&animal[1], &animal[n + 1], cmpX_animal);

  cin >> m;
  for (int i = 1; i <= m; ++i) {
    int xLo, yLo, xHi, yHi;
    cin >> xLo >> yLo >> xHi >> yHi;

    int timeLo = FindLo(yLo, true);
    int timeHi = FindHi(yHi, true);
    int posLo = FindLo(xLo, false);
    int posHi = FindHi(xHi, false);

    posLo = animal[posLo].normX;
    posHi = animal[posHi].normX;

    int localAns;
    if (posLo and timeLo) {
      localAns = RootAtTime[timeHi]->query(posLo, posHi);
      localAns -= RootAtTime[timeLo]->query(posLo, posHi);
    }
    else if (!posLo and timeLo) {
      localAns = RootAtTime[timeHi]->query(1, posHi);
      localAns -= RootAtTime[timeLo]->query(1, posHi);
    }
    else if (posLo and !timeLo) {
      localAns = RootAtTime[timeHi]->query(posLo, posHi);
    }
    else if (!posLo and !timeLo) {
      localAns = RootAtTime[timeHi]->query(1, posHi);
    }

    cout << localAns << '\n';
  }
  return 0;
}