Cod sursa(job #1811705)

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

using namespace std;

const int BUFF_SIZE = (1 << 17);

FILE *fin;
int bp = BUFF_SIZE - 1;
char buff[BUFF_SIZE];

inline void next_char() {
  if (++bp == BUFF_SIZE) {
    fread(buff, 1, BUFF_SIZE, fin);
    bp = 0;
  }
}

inline int get_num() {
  int num = 0, semn = 1;
  while (isdigit(buff[bp]) == 0 && buff[bp] != '-')
    next_char();
  if (buff[bp] == '-') {
    semn = -1;
    next_char();
  }
  while (isdigit(buff[bp])) {
    num = num * 10 + buff[bp] - '0';
    next_char();
  }
  return num * semn;
}

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 = (l + r) / 2, 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 = 2e5;

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()
{
    FILE *fout;
    int n, m, i, p, x1, y1, x2, y2;
    fin = fopen("zoo.in", "r");
    n = get_num();
    for (i = p = 0; i < n; ++i)
      v[p++] = {get_num(), get_num(), 0, 1, 0, 0};
    m = get_num();
    for (i = 0; i < m; ++i) {
      x1 = get_num(); y1 = get_num(); x2 = get_num(); y2 = get_num();
      v[p++] = {x1, y1, y2, i, -1, -1};
      v[p++] = {x2, y1, y2, i, 1, 1};
    }
    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);
      }
    fout = fopen("zoo.out", "w");
    for (i = 0; i < m; ++i)
      fprintf(fout, "%d\n", ans[i]);
    fclose(fout);
    return 0;
}