1
class Solution {
2
 public:
3
  vector<int> BIT;
4
  int n;
5
  vector<vector<int>> reconstructQueue(vector<vector<int>> &people) {
6
    n = people.size();
7
    BIT = vector<int>(n + 1, 0); // BIT[i+1] recorded the res[i] information
8
                                 // because BIT[0] is not used.
9
    for (int i = 2; i <= n; i++)
10
      update(i, 1); // BIT[1] is the 0th empty position, so we didn't add 1
11
    sort(people.begin(), people.end(), cmp);
12
    vector<vector<int>> res(n, vector<int>());
13
    for (int i = 0; i < n; i++) {
14
      int l = 0, r = n;
15
      while (l < r) {
16
        int mid = l + (r - l) / 2;
17
        if (getsum(mid + 1) < people[i][1])
18
          l = mid + 1; // we need get the index mid empty information, but
19
                       // actually it's stored in BIT[mid+1]
20
        else
21
          r = mid;
22
      }
23
      res[l] = people[i];
24
      update(l + 1, -1);
25
    }
26
    return res;
27
  }
28
  void update(int x, int v) {
29
    for (int i = x; i <= n; i += (i & -i)) {
30
      BIT[i] += v;
31
    }
32
  }
33
  int getsum(int x) {
34
    int sum = 0;
35
    for (int i = x; i > 0; i -= (i & -i)) {
36
      sum += BIT[i];
37
    }
38
    return sum;
39
  }
40
  static bool cmp(vector<int> &p1, vector<int> &p2) {
41
    if (p1[0] != p2[0])
42
      return p1[0] < p2[0];
43
    else
44
      return p1[1] > p2[1];
45
  }
46
};