Overview of Problem

This problem is an exercise of a data structure called Priority Queue (Heap). This is implemented as heapq in Python, or priority_queue in C++.

---

Notes: Max- and Min- Heap

heapq in Python is a min-heap, which maintains the “minimum value” by default; meanwhile, priority_queue in C++ is a max-heap, which maintains the “maximum value” by default.

Thus, when we want to take out smaller values first in C++ (as in this problem), we need the following type arguments on declaration:

priority_queue<int, vector<int>, greater<int>> que;

---

What Heap Can Do

While detailed methods and complexity vary depending on implementation, a heap roughly supports the following operations. Let \(N\) be the number of elements in the heap when an operation is performed.

1. Retrieve the minimum value

• Retrieves the minimum value in the heap (without removing).
• Complexity: \(O(1)\)
• Python: que[0]
• C++: que.top()

2. Take out the minimum value

• Removes the minimum value in the heap.
• Complexity: \(O(\log N)\)
• Python: heappop(que)
• C++: que.pop()

3. Insert an element

• Inserts an element into the heap.
• Complexity \(O(\log N)\)
• Python : heappush(que, x)
• C++ : que.push(x)

---

Implementation

In case of our problem, the problem can be solved by by implementing a simulation that performs:

• Type \(1\)

  Insert \(h\) to the heap.

• Type \(2\)

  Retrieve the minimum value, and remove it if it \(h\) or less. Repeat it until it is not \(h\) or less.

This can be implemented as follows:

Implementation in Python

from heapq import heappop, heappush

que = []
q = int(input())
for i in range(q):
    t, h = map(int, input().split())
    if t == 1:
        heappush(que, h)
    else:
        while que and que[0] <= h:
            heappop(que)
    print(len(que))

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    int q; cin >> q;
    priority_queue<int, vector<int>, greater<int>> que;
    for(int i=0; i<q; i++){
        int t, h; cin >> t >> h;
        if (t == 1){
            que.push(h);
        }else{
            while(!que.empty() and que.top() <= h){
                que.pop();
            }
        }
        cout << que.size() << endl;
    }
}

---

Complexity

The complexity can be analyzed as follows.

• Insertion

  This occurs once per one type-\(1\) query, for a total of \(O(N)\) times.

• Removal

  One may feel that computational complexity may bloat up because we may remove many elements in a type-\(2\) query.

  However, once an element is removed, it cannot be removed again, so “the number of removals” must be not greater than “the number of insertions.” Thus, it occurs a total of \(O(N)\) times.

• Retrieval of minimum value

  It is almost the same as the number of removals. In a type-\(2\) query, there may be an element that is referenced as the minimum value, but not removed.

  However, such an element exists at most one per a query, so the number of occurrences is at most \(Q\) times more than the removal count. Thus, it is bounded by \(O(Q)\).

Hence, the complexity is \(O(Q \log Q)\).