1
class Solution {
2
 public:
3
  vector<int> prefix_sum;
4
  vector<vector<int>> rects_vec;
5
  int total = 0;
6

7
  Solution(vector<vector<int>> &rects) {
8
    int cur = 0;
9
    for (int i = 0; i < rects.size(); ++i) {
10
      cur += (rects[i][2] - rects[i][0] + 1) * (rects[i][3] - rects[i][1] + 1);
11
      prefix_sum.push_back(cur);
12
    }
13
    rects_vec = rects;
14
    total = cur;
15
  }
16

17
  vector<int> pick() {
18
    int l = 0, r = prefix_sum.size() - 1, mid = 0;
19
    int rand_num = rand();
20
    int target = (rand_num % total) + 1;
21

22
    while (l <= r) {
23
      mid = l + (r - l) / 2;
24
      if (prefix_sum[mid] < target)
25
        l = mid + 1;
26
      else
27
        r = mid - 1;
28
    }
29

30
    return {rand_num % (rects_vec[l][2] - rects_vec[l][0] + 1) + rects_vec[l][0],
31
            rand_num % (rects_vec[l][3] - rects_vec[l][1] + 1) + rects_vec[l][1]};
32
  }
33
};