leetcode-go/poj/2528.mayors-posters/main.cc

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 10000;
const int L = 10000000;

int id[2 * N];
int hash[L + 1];

struct Post {
  int l;
  int r;
};

Post poster[N];

struct TNode {
  bool val;
  int beg;
  int end;
  TNode *l;
  TNode *r;
  int mid() { return beg + (end - beg) / 2; }
};

TNode tree[8 * N]; // May be 2 * len(id) of intervals, so 2 * 2 * len(id)
int tid;

TNode *build_tree(TNode *root, int beg, int end) {
  root->beg = beg;
  root->end = end;
  root->val = false;
  if (beg != end) {
    root->l = build_tree(&tree[tid++], beg, root->mid());
    root->r = build_tree(&tree[tid++], root->mid() + 1, end);
  }
  return root;
}

bool query(TNode *root, int beg, int end) {
  if (root->val) return false;
  if (root->beg == beg && root->end == end) {
    return root->val = true;
    return true;
  }
  bool res;
  if (root->mid() < beg) {
    res = query(root->r, beg, end);
  } else if (end <= root->mid()) {
    res = query(root->l, beg, end);
  } else {
    // Do NOT use the short cut operator!
    bool b1 = query(root->l, beg, root->mid());
    bool b2 = query(root->r, root->mid() + 1, end);
    res = b1 || b2;
  }
  if (root->l->val && root->r->val) root->val = true;
  return res;
}

int main() {
  int c, n;
  scanf("%d", &c);
  while (c--) {
    scanf("%d", &n);
    int k = 0;
    for (int i = 0; i < n; i++) {
      scanf("%d %d", &poster[i].l, &poster[i].r);
      id[k++] = poster[i].l;
      id[k++] = poster[i].r;
    }
    sort(id, id + k);
    k = unique(id, id + k) - id;
    int intervals = 0;
    for (int i = 0; i < k; i++) {
      hash[id[i]] = intervals;
      if (i < k - 1) {
        if (id[i] + 1 == id[i + 1])
          intervals++;
        else // !!Really important
          intervals += 2;
      }
    }
    tid = 0;
    TNode *root = &tree[tid++];
    build_tree(root, 0, intervals);
    int cnt = 0;
    for (int i = n - 1; 0 <= i; i--)
      if (query(root, hash[poster[i].l], hash[poster[i].r])) cnt++;
    printf("%d\n", cnt);
  }
  return 0;
}