Zcmu--1390: queue problem (1)

Description

Given a queue q, Each element in the queue has two attributes name and pri. For queues 3 The operations in are : 1 name pri Represents adding... To the queue (name,pri) This element . 2 Represents in the output queue pri The highest element name And remove the element from the queue . 3 Represents in the output queue pri Of the lowest element name And remove the element from the queue . Suppose the queue is initially empty , And all elements name The values are different ,pri Values also vary . Given a number of operations , about 2 and 3 The operation outputs the name.

Input

Each line of input represents an operation , If the input is 0 End .(1<=name,pri<=10^6)

Output

For each 2 and 3 operation , Output the corresponding value . If there are no elements in the queue, output 0.

Sample Input

2

1  20  14

1  30  3

2

1  10  99

3

2

2

0

Sample Output

0

20

30

10

0

analysis ： Because it will be based on pri Maximum value to output name , This one uses set It's very convenient , because set It will automatically sort and store , We can quickly find the most value in the queue , As for the output corresponding name, one-on-one , So we use map It's very convenient ！

​
#include <stdio.h> 
#include <map>
#include <set>
using namespace std;
int main()
{
	map<int,int>mp;
	set<int>st;
	int z,a,b;
	while(~scanf("%d",&z),z!=0){
		if(z==1){		// Instructions 1 
			scanf("%d%d",&a,&b);
			st.insert(b);	// Deposit in set in  
			mp[b]=a;		// Corresponding settings name 
		}else if(z==2){	// Instructions 2 
			if(st.size()){	// If it's not empty  
				printf("%d\n",mp[*st.rbegin()]);//*st.rbegin() Represents the last element value  
				st.erase(--st.end());	// Delete the last element  
			}else printf("0\n");	// Null output 0 
		}else{		// Instructions 3 
			if(st.size()){	// ditto  
				printf("%d\n",mp[*st.begin()]);
				st.erase(st.begin());
			}else printf("0\n");
		}
	}
	return 0;
}

​