[백준] 7662 이중 우선순위 큐

https://www.acmicpc.net/problem/7662

7662번: 이중 우선순위 큐

 

1.  I 일때 값을 넣어주고, 들어왔음을 확인시켜준다. 

2. D일때는 값에다가 들어왔음을 표시해주고 최대값, 최소값에 맞게 POP해준다. 

3. 출력은 들어왔음을 표시해준것은 다 pop을 해주고 top값에 있는 값을 출력하준다. 

#include <iostream>
#include <queue>
#include <vector>
#include <deque>
#include <algorithm>
#include <functional>
using namespace std;
bool visited[1000001];
int T;


char ch;
int num;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;


	for (int i = 0; i < T; i++) {
		int k;
		cin >> k;
		
		priority_queue<pair<int, int>> pq_max;
		priority_queue<pair<long long int, long long int>, vector<pair<long long int, long long int>>, greater<pair<long long int, long long int>>>pq_min;

		for (int j = 0; j < k; j++) {

			cin >> ch >> num;
			if (ch == 'I') {
				
				pq_max.push({ num , j });
				pq_min.push({ num , j });
				visited[j] = true;

			}
			else {
				if (num == 1) {
					{
						while (!pq_max.empty() && !visited[pq_max.top().second]) {
							pq_max.pop();
						}
						if (!pq_max.empty()) {
							visited[pq_max.top().second] = false;
							pq_max.pop();
						}
					}


				}
				else
				{

					while (!pq_min.empty() && !visited[pq_min.top().second])
					{
						pq_min.pop();
					}
					if (!pq_min.empty()) {
						visited[pq_min.top().second] = false;
						pq_min.pop();
					}
				}
			}
		}


		while (!pq_max.empty() && !visited[pq_max.top().second])

			pq_max.pop();

		while (!pq_min.empty() && !visited[pq_min.top().second])

			pq_min.pop();



		if (pq_min.empty()&& pq_max.empty())

			cout<< "EMPTY\n";

		else

			cout<< pq_max.top().first<< " " << pq_min.top().first<< "\n";
	}

	return 0;

}