Booking Concert Tickets in Groups LeetCode solution in C++

1
class BookMyShow {
2
  int occ = -1; // No row occupied initially
3
  vector<long long> sumTree, maxTree;
4
  int treeSize = 0, rowSeats = 0;
5

6
 public:
7
  BookMyShow(int n, int m) {
8
    // Seg tree size
9
    this->treeSize = (int)2 * pow(2, ceil((double)log2(n)));
10
    sumTree.resize(treeSize);
11
    maxTree.resize(treeSize);
12

13
    this->rowSeats = m;
14
    constructSumTree(m);
15
    constructMaxTree(m);
16
  }
17

18
  void constructSumTree(int m) {
19
    int n = this->treeSize / 2;
20

21
    // Filling the leaves
22
    for (int i = n; i < 2 * n; i++) this->sumTree[i] = (long long)m;
23

24
    // Forming the higher nodes
25
    for (int i = n - 1; i >= 1; i--)
26
      this->sumTree[i] = this->sumTree[2 * i] + this->sumTree[2 * i + 1];
27
  }
28

29
  void constructMaxTree(int m) {
30
    int n = this->treeSize / 2;
31

32
    // Filling the leaves
33
    for (int i = n; i < 2 * n; i++) this->maxTree[i] = (long long)m;
34

35
    // Forming the higher nodes
36
    for (int i = n - 1; i >= 1; i--)
37
      this->maxTree[i] = max(this->maxTree[2 * i], this->maxTree[2 * i + 1]);
38
  }
39

40
  long long rangeSum(int minRow, int maxRow) {
41
    long long sum = 0;
42
    int n = treeSize / 2;
43
    minRow += n;
44
    maxRow += n;
45
    while (minRow <= maxRow) {
46
      if (minRow % 2 == 1) sum += this->sumTree[minRow++]; // Right child
47
      if (maxRow % 2 == 0) sum += this->sumTree[maxRow--]; // Left child
48
      minRow /= 2;
49
      maxRow /= 2;
50
    }
51

52
    return sum;
53
  }
54

55
  void updateSumTree(int index, int newValue) {
56
    int n = this->treeSize / 2;
57
    int temp = index;
58
    index += n;
59
    this->sumTree[index] = newValue; // Update leaf
60
    index /= 2;
61
    while (index > 0) {
62
      this->sumTree[index] = this->sumTree[2 * index] + this->sumTree[2 * index + 1];
63
      index /= 2;
64
    }
65
  }
66

67
  long long rangeMax(int minRow, int maxRow) {
68
    long long ans = 0;
69
    int n = this->treeSize / 2;
70
    minRow += n;
71
    maxRow += n;
72
    while (minRow <= maxRow) {
73
      if (minRow % 2 == 1) ans = max(ans, this->maxTree[minRow++]); // Right child
74
      if (maxRow % 2 == 0) ans = max(ans, this->maxTree[maxRow--]); // Left child
75
      minRow /= 2;
76
      maxRow /= 2;
77
    }
78

79
    // cout<<"range max over"<<'\n';
80
    return ans;
81
  }
82

83
  void updateMaxTree(int index, int newValue) {
84
    int n = this->treeSize / 2;
85
    int temp = index;
86
    index += n;
87
    this->maxTree[index] = newValue; // Update leaf
88
    index /= 2;
89
    while (index > 0) {
90
      this->maxTree[index] = max(this->maxTree[2 * index], this->maxTree[2 * index + 1]);
91
      index /= 2;
92
    }
93
  }
94

95
  vector<int> gather(int k, int maxRow) {
96
    int minRow = occ + 1;
97
    if (maxRow < minRow) return {};
98
    if (rangeMax(minRow, maxRow) < k) return {};
99

100
    int minIndex = maxRow;
101
    int seats = 0;
102
    int low = minRow, high = maxRow;
103
    while (low <= high) {
104
      int midRow = (low + high) / 2;
105
      int maxSeats = rangeMax(minRow, midRow);
106
      if (maxSeats >= k) {
107
        high = midRow - 1;
108
        seats = maxSeats;
109
        minIndex = midRow;
110
      } else
111
        low = midRow + 1;
112
    }
113

114
    int r = minIndex, c = this->rowSeats - seats;
115

116
    // Updatng the segment trees
117
    this->updateMaxTree(minIndex, seats - k);
118
    this->updateSumTree(minIndex, seats - k);
119
    return {r, c};
120
  }
121

122
  bool scatter(int k, int maxRow) {
123
    int minRow = occ + 1;
124
    if (maxRow < minRow) return false;
125
    if (rangeSum(minRow, maxRow) < k) return false;
126

127
    int minIndex = maxRow;
128
    long long seats = 0;
129
    int low = minRow, high = maxRow;
130
    while (low <= high) {
131
      int midRow = (low + high) / 2;
132
      long long rangeSeats = rangeSum(minRow, midRow);
133
      if (rangeSeats >= k) {
134
        high = midRow - 1;
135
        seats = rangeSeats;
136
        minIndex = midRow;
137
      } else
138
        low = midRow + 1;
139
    }
140

141
    // Updating the occupied rows
142
    occ = minIndex - 1;
143

144
    // Updating the segment trees
145
    this->updateSumTree(minIndex, seats - k);
146
    this->updateMaxTree(minIndex, seats - k);
147
    return true;
148
  }
149
};
150

151
/**
152
 * Your BookMyShow object will be instantiated and called as such:
153
 * BookMyShow* obj = new BookMyShow(n, m);
154
 * vector<int> param_1 = obj->gather(k,maxRow);
155
 * bool param_2 = obj->scatter(k,maxRow);
156
 */