Description

Please maintain a max-heap, which stores integers and is able to support following operations:

(1) PUSH k – Insert an integer k into the heap. k will fit in a 32-bit signed integer.

(2) POP – Delete the maximum element from the heap.

(3) TOP – Print the maximum element in the heap.

Input

There is only one set of commands. Each command occupies a line, and the total number of commands is less than or equal to 500000. You may assume that the number of elements stored in the heap will be no more than 10000 at any time.

Output

For each “TOP” command, output a line containing the value of the element on the top of the heap. In case that the heap is empty, print ”Null” instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We want to implement a templated circular buffer class, circular_buffer<T>, that supports push_back(), pop_front(), size(), and the [] operator.

A circular buffer behaves similar to a circular queue introducted in the Data Struecutre textbook except that a newly inserted element may replace an old element if the buffer is full.  Specifically, if a circular buffer is full, the front element of the buffer is popped before a new element is inserted.

Please use the following partial code to complete this homework.

---

#include <iostream>

using namespace std;

/* Code for our templated circular buffer class goes here */

int main()
{
    int capacity;
    cin >> capacity;
    circular_buffer<int> cbi(capacity);

    int N;
    cin >> N;
    for(int i=0; i<N; i++){
        string cmd;
        cin >> cmd;
        if(cmd=="push_back"){
            int data;
            cin >> data;
            cbi.push_back(data);
        }else if(cmd=="pop_front"){
            cbi.pop_front();
        }else if(cmd=="print"){
            for(int j=0; j<cbi.size(); j++){
                cout << cbi[j] << endl;
            }
            cout << "----" << endl;
        }
    }
    return 0;
}

---

 

Input

Please note that the partial code can handle input and output already.  We do not need to rewrite this part of input/output handling code.  We only need to focus on the circular buffer class.  Input and output format are listed for reference only.

The first input integer indicates the capacity of the capacity of the instantiated circular buffer.

The second input integer indicates the number of commands used to test the buffer.

Commands include

push_back k : insert an interger, k, using the push_back() operator

pop_pront : remove an element, using the pop_front() operator

print : print out all elements in the buffer using the [] operator and a loop.

 

 

Output

Please note that the partial code can handle input and output already.  We do not need to rewrite this part of input/output handling code.  We only need to focus on the circular buffer class.  Input and output format are listed for reference only.

Upon a print command all elements in the buffer are printed out, starting at the front and working toward the back.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

I have broken many girls' hearts into pieces. But none of them mad at me. None.

~ by anonymous surgeon

You're a surgeon, you need to mend those girls' hearts. Therefore you need a data structure to support some functions.

This question is about maintain a set that contains only integers.

There will be n instructions.

Each instruction will be either:

insert:

Insert a new element ai into the set. Note that if the element has already in the set, do nothing.

 

print:

print all the element in the set in increasing order.

 

min:

print the number in the set that is the smallest. If there's no number, do nothing.

 

range_erase:

You will have two integer l, r.

You need to erase all the elements ai in the set that l <= ai <= r

Hint: You can solve this question very fast by using std::set .

These are some functions you may use in your code:

set.begin(), set.size(), set.erase(), set.lower_bound(), set.upper_bound(), set.insert(). To traverse through your set, you may also need iterator or type auto(only in c++11!)

You can also solve this question in C.

 

 

 

 

Input

the input will contain several lines.

The first line only contains an integer n (1 <= n <= 5000)

The following are n lines.

Each lines contains a instruction list above.

Note that ai (0 <= ai <= 10^9)

Output

 

For each print instruction, print all the number in the set in increasing order.

Each number is separated by a single blank.(No blank at the the end!)

Remember to print \n at the end of output

 

For each min instruction, print the smallest number in the set.

Remember to print \n at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss