| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13451 | K-th largest |
|
| 13872 | Black Box |
|
| 13879 | Tree-Graph Inheritance |
|
Description
Mr. Kuo is an adventurer. One day, he finds a sequences of operations and an empty set S.
Each operation is one of the following two types,
- Insert x：insert x into S. Duplicate element is legal.
- Query x k：Among the elements of S that are greater or equal to x, what is the k-th smallest value？
Mr. Kuo is curious about the answer to each operation 2, so he asks for your help.
Hint：You can refer to C++ upper_bound function.
Input
The input consists of multiple lines.
Each line is given in one of the following two format：
- Insert x
- Query x k
There will be at most 100000 operations in the sequences.
1 ≤ x ≤ 109
1 ≤ k ≤ 5
Output
For each operation of type 2, print the k-th smallest value among the elements of S that are greater than or equal to x.
If there are less than k elements of S that are greater than or equal to x, then print "-1".
Remember to print '\n' at the end of each line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
On your way to the Delta Building for class as usual, you accidentally tripped. Just when you were angry and wanted to kick the stone that tripped you away, you found that it was not an ordinary stone, but a magical black box.
The box is amazing, you can add or remove some numbers to it, and you can even ask it some questions. 'The box is so cool, if I can make a same one, I can definitely sell it for a lot of money', you think.
You can do five operations to the black box:
- 1 k x: add number x into the box k times
- 2 k x: remove number x in the box k times, if number x in box is fewer than k, just remove all x
- 3 x: ask how many x are in the box
- 4: ask the maximum number in the box, if there are no number in the box, the box will answer you "The box is empty."
- 5: ask the minimum number in the box, if there are no number in the box, the box will answer you "The box is empty."
If you want to become rich, please make a same magical black box.
Input
The first line contains an integer N -- the number of operations you will do to the black box.
The next N lines will be the operations as above.
1 <= N <= 2e5.
1 <= k <= 1e9.
-1e9 <= x <= 1e9.
Output
For the third operation, please output how many x are in the box.
For the fourth operation, please output the maximum number in the box, if there are no numbers in the box, output "The box is empty."
For the fifth operation, please output the minimum number in the box, if there are no numbers in the box, output "The box is empty."
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In Object-Oriented Programming (OOP), the inheritance among classes represent ``is-a'' relationships for abstractions. Graphs and trees are both fundamental for computer science. In fact, a tree is a special case of a graph that is connected as well as acyclic.
In fact, we often implement trees and graphs by similar means in practice. For instance, we tend to store trees and graphs by adjacent matrice or lists. Moreover, we traverse trees and graphs in alike ways.
For simplicity, we only consider basic operations on trees and graphs. You need implement BFS traversal for a graph starting from a given source and returning the distance to all other vertices so that trees could inherit that method. Furthermore, you should find the diameter (the longest distance in a tree that we've encountered several times but solved by DFS then) by BFS traversal.
Input
Please see the instructions in the header. BFS traversal would be called with the source. As for diameter, there's no parameter.
It's guaranteed that the graph is connected and simple, and that the number of vertices of a tree is less than 100000.
Output
For BFS traversal, you should return a vector of n integers indicating the minimum distance from source.
As for the diameter, you should return an integer.