Restoran

Potrebno je napisati program koji će pomoći radnicima u restoranu. Program treba da realizuje dva upita:

• \(p\ x\) - pristigla je porudžbina čija je cena \(x\)
• \(k\) - kuhinja želi da preuzme najskuplju i najraniju porudžbinu i počne da ih priprema

Ukoliko su najskuplja i najranija porudžbina jedna ista porudžbina, preuzima se samo ona. Ukoliko nema pristiglih porudžbina, upit \(k\) nema efekta. Na kraju obrade svih upita potrebno je ispisati cenu najskuplje porudžbine koja nije obrađena.

Opis ulaza

Sa standardnog ulaza učitava se broj porudžbina \(n\), a zatim i \(n\) upita u gorenavedenom formatu.

Opis izlaza

Na standardni izlaz ispisati cenu najskuplje porudžbine koja nije obrađena. U slučaju da nije preostala ni jedna porudžbina, ispisati -1.

Primer

Ulaz

7
p 350
p 200
p 500
k
p 300
p 250
k

Izlaz

250

Objašnjenje

Nakon prvog upita \(k\) biće preuzete porudžbine sa cenama 350 (najranija) i 500 (najskuplja).

Nakon drugog upita \(k\) biće preuzete porudžbine sa cenama 200 (najranija) i 300 (najskuplja).

Rešenje

#include <iostream>
#include <queue>
#include <unordered_set>

using namespace std;

int main() 
{
    int n; cin >> n;

    queue<int> q;
    priority_queue<int> pq;
    unordered_set<int> s;

    while(n--){
        char op; cin >> op;
        if(op == 'p'){
            int x; cin >> x;
            q.push(x); pq.push(x); s.insert(x);
        } if(op == 'k'){
            while(!pq.empty() && s.find(pq.top()) == s.end())
                pq.pop(); 

            if(!pq.empty()){
                int x1 = pq.top(); pq.pop();
                s.erase(x1);
            }

            while(!q.empty() && s.find(q.front()) == s.end())
                q.pop();   

            if(!q.empty()){
                int x2 = q.front(); q.pop();
                s.erase(x2);
            }
        }
    }

    if (pq.empty()) {
        cout << -1 << endl;
    } else {
        cout << pq.top() << endl;
    }

    return 0;
}