Submit | All submissions | Best solutions | Back to list |
CMG - Collecting Mango |
One day after storm mina went to pick up mangoes in the garden with a basket. She began to pick up mangoes from the garden. And if she wants, she can throw away the last picked up mango from the basket. In this way, mina kept picking up mangoes. She brought you with her to keep track of the biggest size of mango in the basket at that time. At any moment Mina can ask you about the biggest size of mango. Your job is to help Mina.
Since you are a good programmer, so you write a program by which you are easily able to answer the question of Mina.
During picking up mangoes, Mina can have 3 types of question/instruction for you.
- Type 1: put an ‘x’ size mango in the basket, which is picked up form garden.
- Type 2: Throw out last picked up mango. (There can be consecutive throw out operation.)
- Type 3: Ask for the biggest mango size in the basket at that moment.
Input
The first line contains a positive integer T, number of test case. In the following each case start with a positive integer N, which is number of question/operation Mina will ask during picking up mangoes. Next N lines will contain 3 types of operations (A, R, Q). A x, here x is picked up mango size. R, throw out last picked up mango from basket. Q Find out the biggest size mango.
Output
For each case, first print the case number and print the answer of Mina’s question. Whenever the basket is empty, then Mina’s question’s answer will be “Empty”.
Constraints
- 1<=T<=25
- 1<=N<=100000
- 1<=x<=100000
Example
Input: 2 6 A 10 A 5 Q A 100 R Q 6 A 5 Q R Q R R Output: Case 1: 10 10 Case 2: 5 Empty
Added by: | Anick |
Date: | 2016-04-24 |
Time limit: | 0.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: GOSU |
Resource: | Own problem. Used in NHSPC 2016 Final Round. More about NHSPC: http://www.nhspc.org/ |
hide comments
|
||||||
2016-08-11 17:08:40 Dignesh P R
Guys, Any hints? My solution runs in less than 0.2s for 100K operations but still getting TLE. |
||||||
2016-08-08 06:09:03 Dignesh P R
@Piyush Kumar : Can you please provide me the test case you tried to give 3/4 the of time? |
||||||
2016-08-03 06:58:35 Dignesh P R
Using vector. Constant time add & throw function and log n time max function gives tle. any better approach? Last edit: 2016-08-03 06:58:58 |
||||||
2016-07-06 13:52:01 Piyush Kumar
No need to use fast I/O. Scanf/Printf with optimal solution(O(n)) passes in 3/4th of the time limit. |
||||||
2016-06-22 11:30:54
simple question but needs some seriously fast io methods. dont forget to optimize output method as well caused me atleast 15 tle's |
||||||
2016-06-16 10:27:15 rccroshan1
The problem focuses more on I/O rather than data structures. The time limit should not be so strict. |
||||||
2016-05-21 17:39:50 RAJDEEP GUPTA
Had to use fast I/O. O(n) |
||||||
2016-05-02 21:41:15 Archit Gupta
Learnt a new thing. While taking input of characters via scanf() put space before %c it will ignore the space. |
||||||
2016-05-02 18:01:25 Amir Najjar
Heck of a problem. Best case is O(t * n * log n), any other idea on how to solve this? |
||||||
2016-04-30 17:23:18
Finally AC. I think I broke all my past records of getting wrong answers on this one. Such a relief to see the green light. :) Last edit: 2016-04-30 23:14:31 |