**Problem**

Chef has opened up a new restaurant. He picks out the positive reviews and posts it on the website of the restaurant. A review is represented by an integer which is the overall rating of the restaurant as calculated by that particular review. A review is considered to be positive if it is among the top one-third of the total reviews when they are sorted by their rating. So here is what the Chef wants from you: Given the reviews (ratings) by different critics, the Chef needs you to tell him what is the minimum rating that his website will be displaying.

The new reviews keep coming in. And the Chef wants your website ratings to be up-to-date. So you should keep updating the ratings there. At any point of time, the Chef might want to know the minimum rating being displayed.

**Example**

Suppose the ratings given by 8 different reviews are as follows:

2 8 3 1 6 4 5 7

Then the top one-third reviews will be 8 and 7. Note that we considered one-third to be 8/3=2 top reviews according to integer division.

###### Input

First line of the input file consists of a single integer N, the number of operations to follow. The next N lines contain one operation each on a single line. An operation can be of 2 types:

1 x

Add a review with rating ‘x’ to the existing list of reviews (x is an integer)

2

Report the current minimum rating on the website

###### Output

For every test case, output a single integer each for every operation of type 2 mentioned above. If no review qualifies as a positive review, print “No reviews yet”.

###### Constraints

1 ≤ N ≤ 250000

1 ≤ x ≤ 1000000000

###### Sample Input

10 1 1 1 7 2 1 9 1 21 1 8 1 5 2 1 9 2

###### Sample Output

No reviews yet 9 9

###### Solution I

**Approach**

This problem could be solved easily by using **Heap** data structure (you could read about Heap data structure here). We will maintain two heaps: **maxHeap (a max heap)** & **topRating** **(a min heap)**. **maxHeap** will be containing bottom 2/3rd ratings in max heap order i.e. maxHeap.front() at any time will give the highest (2/3rd) rating from reviews.

While, **topRating** will be containing top 1/3rd ratings in min heap order i.e. topRating.front() at any time will give the lowest (1/3rd) rating from reviews.

So, whenever a new rating comes, we will be checking in which of the two heaps should this rating go ie.

– if current rating **x** is less than **topRating.front()**, we will add it to **maxHeap**

– else if current rating **x** is greater than **topRating.front()**, we will add it to **topRating**

While doing the aforementioned operations we will also be maintaining the size and order of **topRating** heap, so that **topRating.front()** will always be 1/3rd of the total number of ratings:

– if current rating **x** is greater than **topRating.front()** and less than** maxHeap.front()**, we will add **maxHeap.front()** to ** topRating** and

**x**to

**maxHeap**

– also if

**topRating.size()**becomes greater than 1/3rd the size of total reviews, we will remove the minimum (front) element of

**and add it to**

**topRating****maxHeap**.

**Code Implementation**

```
//
// main.cpp
// Restaurant Rating (Codechef)
//
// Created by Himanshu on 02/11/22.
//
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
long int x, ctr=0, n, pos, T;
vector<long int> maxHeap, topRating;
scanf("%ld", &T);
make_heap(maxHeap.begin(), maxHeap.end());
make_heap(topRating.begin(), topRating.end(), greater<int>());
topRating.push_back(0);
push_heap(topRating.begin(), topRating.end(), greater<int>());
while (T > 0) {
scanf("%ld", &n);
if (n == 1) {
scanf("%ld", &x);
if (x < topRating.front()) {
maxHeap.push_back(x);
push_heap(maxHeap.begin(), maxHeap.end());
//Integer to maintain current
//total number of reviews
ctr++;
//Updating the top 1/3rd rating
if (ctr/3 > topRating.size()) {
topRating.push_back(maxHeap.front());
push_heap(topRating.begin(), topRating.end(), greater<int>());
pop_heap(maxHeap.begin(), maxHeap.end());
maxHeap.pop_back();
}
} else {
//Removing the bottom sentinel
if (topRating.front() == 0) {
pop_heap(topRating.begin(), topRating.end(), greater<int>());
topRating.pop_back();
}
if (maxHeap.size() > 0 && maxHeap.front() > x) {
topRating.push_back(maxHeap.front());
push_heap(topRating.begin(), topRating.end(), greater<int>());
pop_heap(maxHeap.begin(),maxHeap.end());
maxHeap.pop_back();
maxHeap.push_back(x);
push_heap(maxHeap.begin(), maxHeap.end());
} else {
topRating.push_back(x);
push_heap(topRating.begin(), topRating.end(), greater<int>());
}
ctr++;
if (ctr/3 < topRating.size()) {
maxHeap.push_back(topRating.front());
push_heap(maxHeap.begin(), maxHeap.end());
pop_heap(topRating.begin(), topRating.end(), greater<int>());
topRating.pop_back();
}
if (topRating.size() == 0) {
topRating.push_back(0);
push_heap(topRating.begin(), topRating.end(), greater<int>());
}
}
} else {
pos = ctr/3;
if (pos <= 0) {
printf("No reviews yet\n");
} else {
printf("%ld\n",topRating.front());
}
}
T--;
}
return 0;
}
```

**Time Complexity: O(n*logn)**

###### Solution II

This problem could also be solved by using C++ `multiset`

data structure and `advance()`

method of <iterator> class.

**Approach**

Keep inserting the new ratings into the `multiset`

. The minimum rating being displayed can be found by finding the (n/3)^{rd} smallest element in the tree, where n is the total number of reviews in the tree. This solution would have a time complexity of O(log n) for insertion and retrieval of elements. However, it may give TLE (Time Limited Exceeded) on a large input. [1]

**Reference****[1]** ChatGPT