Pasted

#include <vector>
#include "optimization.h"
#include <cassert>
using namespace std;
vector<int> heapMin, heapMax;
vector<int> values, posMin, posMax;
 
void swap_min(int i, int j) {
    swap(posMin[heapMin[i]], posMin[heapMin[j]]);
    swap(heapMin[i], heapMin[j]);
}
 
void swap_max(int i, int j) {
    swap(posMax[heapMax[i]], posMax[heapMax[j]]);
    swap(heapMax[i], heapMax[j]);
}
 
void siftUp_min(int i) {
    while(i > 0) {
        int parent = i % 2 == 0 ? (i - 2) / 2 : (i - 1) / 2;
        if (values[heapMin[parent]] > values[heapMin[i]]) {
            swap_min(i, parent);
        } else {
            break;
        }
        i = parent;
    }
}
 
void siftDown_min(int i) {
    while(i < heapMin.size()) {
        int l = 2 * i + 1, r = 2 * i + 2;
        int minChild = r < heapMin.size() ? (values[heapMin[l]] < values[heapMin[r]] ? l : r) : (l < heapMin.size() ? l : -1);
        if(minChild == -1) break;
        if (values[heapMin[i]] > values[heapMin[minChild]]) {
            swap_min(i, minChild);
        }
        i = minChild;
    }
}
 
void siftUp_max(int i) {
    while(i > 0) {
        int parent = i % 2 == 0 ? (i - 2) / 2 : (i - 1) / 2;
        if (values[heapMax[parent]] < values[heapMax[i]]) {
            swap_max(i, parent);
        } else {
            break;
        }
        i = parent;
    }
}
 
void siftDown_max(int i) {
    while(i < heapMax.size()) {
        int l = 2 * i + 1, r = 2 * i + 2;
        int maxChild = r < heapMax.size() ? (values[heapMax[l]] > values[heapMax[r]] ? l : r) : (l < heapMax.size() ? l : -1);
        if(maxChild == -1) return;
        if (values[heapMax[i]] < values[heapMax[maxChild]]) {
            swap_max(i, maxChild);
        }
        i = maxChild;
    }
}
 
void add(int elem) {
    int iv = values.size();
    int ih = heapMin.size();
    
    values.push_back(elem);
    
    posMin.push_back(ih);
    heapMin.push_back(iv);
    siftUp_min(ih);
    
    posMax.push_back(ih);
    heapMax.push_back(iv);
    siftUp_max(ih);
}
 
int min() {
    return heapMin[0];
}
 
int max() {
    return heapMax[0];
}
 
void delFromMin(int elem) {
    int helem = posMin[elem];
    int he = heapMin.size() - 1;
    swap_min(helem, he);
    heapMin.pop_back();
//    siftDown_min(helem);
    siftUp_min(helem);
}
 
void delFromMax(int elem) {
    int helem = posMax[elem];
    int he = heapMax.size() - 1;
    swap_max(helem, he);
    heapMax.pop_back();
//    siftDown_max(helem);
    siftUp_max(helem);
}
 
int delmin() {
    int m = min();
    int i = heapMin.size() - 1;
    swap_min(0, i);
    heapMin.pop_back();
    siftDown_min(0);
    delFromMax(m);
    return values[m];
}
 
int delmax() {
    int m = max();
    int i = heapMin.size() - 1;
    swap_max(0, i);
    heapMax.pop_back();
    siftDown_max(0);
    delFromMin(m);
    return values[m];
}
 
int main() {
    int n = readInt();
    for (int i = 0; i < n; i++) {
        if(readChar() == 'I') {
            while(readChar() != '(');
            add(readInt()); //readInt also captures )
            assert(getChar() == '\n');
        } else {
            while(readChar() != 'M');
            if(readChar() == 'i') {
                assert(readChar() == 'n');
                assert(getChar() == '\n');
                writeInt(delmin(), '\n');
            } else {
                assert(readChar() == 'x');
                assert(getChar() == '\n');
                writeInt(delmax(), '\n');
            }
        }
    }
    return 0;
}