priority_que part1 - DL Руководство пользователя

13_Gs. Межгалактическая война http://dl.gsu.by/task.jsp?nid=1275848&cid=620

Это стандартная задача на кучу.
Надо иметь ввиду, что Extract извлекает минимум из кучи, поэтому если в команде 2 нужно только показывать минимум то можно просто выводить Heap1 который является минимальным.
Кроме того, в условиях задачи явно не оговорено, но в 6 и 7 тестах производиться команда на удаление при пустой куче. Чтобы их пройти нужно просто ничего не делать в таком случае.

Теоретически можно использовать в качестве кучи multiset

time1.cpp

#include <bits/stdc++.h>
using namespace std;
int main()
{
  multiset<int> s;
  int N,i,a,c;
  cin >> N ;
  for (i=0; i<N; i++)
    {
      cin >> c;
      if (c==1) {cin >> a; s.insert(a);};
      if (c==2) if (s.empty()) cout << -1         << endl;
                   else        cout << *s.begin() << endl;
      if (c==3) { if (not s.empty())a=*s.begin(); s.erase(s.find(a));};
    }
}

Однако в данной задаче количество элементов N = 1 000 000.
А сложность multiset N*LogN получается порядка 20 000 000.
И такое решение не проходит по времени уже второй тест.
В таких случаях лучше использовать priority_que, сложность которой O(N)

time2.cpp

#include <bits/stdc++.h>
using namespace std;
int main()
{
  priority_queue <int> q;
  int N,i,a,c;
  cin >> N ;
  for (i=0; i<N; i++)
    {
      cin >> c;
      if (c==1) {cin >> a; q.push(-a);};
      if (c==2) if (q.empty()) cout << -1       << endl;
                   else        cout << -q.top() << endl;
      if (c==3) if (not q.empty()) q.pop();
    }
}

Однако это решение не прошло по времени 7-ой тест.
Надо ускорить потоковый ввод магическим заклинанием:
iostream::sync_with_stdio(false);
cin.tie(NULL);
И тогда получаем полное решение задачи

all.cpp

#include <bits/stdc++.h>
using namespace std;
int main()
{
  iostream::sync_with_stdio(false);
  cin.tie(NULL);

  priority_queue <int> q;
  int N,i,a,c;

  cin >> N ;
  for (i=0; i<N; i++)
    {
      cin >> c;
      if (c==1) {cin >> a; q.push(-a);};
      if (c==2) if (q.empty()) cout << -1      << endl;
                   else        cout << -q.top() << endl;
      if (c==3) if (not q.empty()) q.pop();
    }
}