MINSTACK - Smallest on the Stack
Every Christmas the good old man can go to every house in the world and leave gifts for the children who have been good throughout the year, but this is only possible because of his magic gift bag. It would be impossible for Santa to carry all the presents in his bag, the volume and weight of them all makes this obviously unfeasible. What actually happens is that your bag is a kind of magical portal to your gift factory at the North Pole. Where the presents are stacked by their elves and Noel always takes the gift from the top of that pile when he accesses his magical bag.
Gifts have a numerical measure of the degree of fun they can provide children, and Santa is always concerned with the least fun gift he will deliver throughout the night because he does not want any child to feel bad about it. you receive. However, this can not be done in advance because throughout the night as the good old man takes gifts from the pile to deliver, others are still being made and placed on the pile. So the most he can know is the value of the least fun present on the stack up to that point.
Your task is, given the sequence of operations done on the stack of gifts, answer Santa's queries about the value of the least entertaining gift on the stack thus far.
Input
The first line of the input contains an integer N (1 ≤ N ≤ 106) corresponding to the number of operations performed on the present stack. The operations can be of three types: "PUSH V" where V (1 ≤ V ≤ 109) is an integer representing the degree of fun of the present being placed on the stack; "POP" which represents that Santa Claus is taking a gift from the cell to deliver and "MIN" representing a Noel query to know the smallest gift value in the stack.
Output
The output consists of a line containing an integer with the smallest present value in the stack for queries of type "MIN" or "EMPTY" for "MIN" and "POP" operations when the stack is empty.
Example
Input: 11 PUSH 5 PUSH 7 PUSH 3 PUSH 8 PUSH 10 MIN POP POP MIN POP MIN Output: 3 3 5
Example
Input: 9 PUSH 100 PUSH 50 MIN PUSH 45 MIN POP MIN POP MIN Output: 50 45 50 100
hide comments
|
tarun_28:
2020-06-01 23:36:09
Implement multiset!! |
|
abhishekv18:
2019-12-24 19:12:24
don't forget to print EMPTY in case of empty stack :-) |
|
kh_q:
2019-11-10 05:58:00
Where I can find solution with c++?? |
|
[Lakshman]:
2019-11-09 04:35:24
@shriman_chetan I got AC with Java without fast IO. |
|
Simes:
2019-11-08 14:39:47
@shriman_chetan: Yes, but that's 1.7 seconds in total across the 10 or so test cases, and each test case is allowed between 1 and 1.2 seconds.
|
|
|
Simes:
2019-11-08 11:16:18
There are Java solutions https://www.spoj.com/ranks/MINSTACK/lang=JAVA |
|
scruple:
2019-05-31 11:45:54
50th! |
|
nadstratosfer:
2019-03-19 08:36:55
Adarsh, this problem features large input so correct complexity might not be enough if the code style is poor, resulting in high constant factor, or IO method slow. Try various input methods at INTEST and see if you can get anywhere close to the Java top there: https://www.spoj.com/ranks/INTEST/lang=JAVA . This should help, albeit psetter is correct that it's absolutely possible to get AC without fast IO, or with a slow language. |
|
adarsh18213:
2019-03-03 12:32:45
I'm new to SPOJ.
|
| Added by: | Francisco Elio Parente Arcos Filho [UEA] |
| Date: | 2018-12-24 |
| Time limit: | 1s-1.200s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
RSS