Stock Market by phantom11

Problem statement

Albert is a school teacher and he is correcting the examination answer sheets of his class. He is getting bored and so decides to play a game. He has three options in this game:

  • He can choose to correct a new answer sheet. After correcting it and giving it a score, he places this answer sheet on the top of the pile.
  • He can remove the answer sheet that is on the top of the pile provided there is atleast one answer sheet in the pile.
  • He may want to know who has scored the minimum of all students whose answer sheets are in the pile.
Since there can be large number of answer sheets, you as Albert's assistant, have to write a program to help him.

Input & Output

The first line contains the number of test cases T (≤ 50). The description of T test cases follows. Each test case begins with a line with an integer Q (≤ 10000), the number of operations. The next Q lines describe the operations:

  • 1 x : 1 denotes that Albert wants to add an answer sheet to the top of the pile. It's score is x.
  • 2 : denotes that Albert wants to throw away the topmost answer sheet in the pile. This operation will only be given if the pile has at least one answer sheet.
  • 3 : denotes Albert wants to know the minimum score currently in the pile. This operation will also be given only when there is at least one answer sheet in the pile.

For every operation of type 3, answer one line with an integer, the minimum score currently in the pile.

Sample Input
1
7
1 3
1 -1
1 7
3
2
2
3
Sample Output
-1
3
Use 2 stacks, one to represent the actual current pile at every instance (referred as Main), and another stack (Min stack) which is updated only when the current element to be pushed is ≤ all the elements in the Main stack. Whenever a operation of type 3 is encountered, we only have to peek the topmost element of the Min Stack. When a type 2 operation is encountered, we also have to pop an element from Min Stack if topmost(Min Stack) = topmost(Main Stack)


To try out your code



Sign in

Sign up