Cod sursa(job #1811736)

Utilizator cella.florescuCella Florescu cella.florescu Data 21 noiembrie 2016 15:41:31
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXC = 2e9;

struct Node {
  int val;
  Node *ls, *rs;
  Node (int v, Node *p1, Node *p2) : val(v), ls(p1), rs(p2) {};
} *nil = new Node(0, nullptr, nullptr), *root = new Node(0, nil, nil);

int x, y;

void update(Node *node, int l, int r) {
  if (l == r) {
    ++node->val;
    return;
  }
  long long mid = (1LL * l + r + 2LL * MAXC) / 2 - MAXC;
  if (x <= mid) {
    if (node->ls == nil)
      node->ls = new Node(0, nil, nil);
    update(node->ls, l, mid);
  } else {
    if (node->rs == nil)
      node->rs = new Node(0, nil, nil);
    update(node->rs, mid + 1, r);
  }
  node->val = node->ls->val + node->rs->val;
}

int query(Node *node, int l, int r) {
  if (x <= l && r <= y)
    return node->val;
  int mid = (1LL * l + 1LL * r) / 2LL, val1 = 0, val2 = 0;
  if (x <= mid)
    if (node->ls == nil)
      val1 = 0;
    else
      val1 = query(node->ls, l, mid);
  if (mid + 1 <= y)
    if (node->rs == nil)
      val2 = 0;
    else
      val2 = query(node->rs, mid + 1, r);
  return val1 + val2;
}

const int MAXQ = 3e5;

struct Query {
  int x, y1, y2, q, s, t;
  bool operator < (const Query &other) const {
    if (x == other.x)
      return t < other.t;
    return x < other.x;
  }
} v[MAXQ];

int ans[MAXQ];

int main()
{
    int n, m, i, p, x1, y1, x2, y2;
    ifstream fin("zoo.in");
    fin >> n;
    for (i = p = 0; i < n; ++i) {
      fin >> x1 >> y1;
      v[p++] = {x1, y1, 0, 1, 0, 0};
    }
    fin >> m;
    for (i = 0; i < m; ++i) {
      fin >> x1 >> y1 >> x2 >> y2;
      v[p++] = {x1, y1, y2, i, -1, -1};
      v[p++] = {x2, y1, y2, i, 1, 1};
    }
    fin.close();
    sort(v, v + p);
    for (i = 0; i < p; ++i)
      if (v[i].t) {
        x = v[i].y1; y = v[i].y2;
        ans[v[i].q] += v[i].s * query(root, -MAXC, MAXC);
      } else {
        x = v[i].y1;
        update(root, -MAXC, MAXC);
      }
    ofstream fout("zoo.out");
    for (i = 0; i < m; ++i)
      fout << ans[i] << '\n';
    fout.close();
    return 0;
}