binary_tree.cpp

#include <cmath>
#include <iostream>
#include <set>
#include <vector>
#include <utility>
#include <string>

int readNum()
{
	int n;
	std::cin >> n;
	std::cin.ignore();
	return n;
}

std::vector<int> readNums(const std::size_t size)
{
	std::vector<int> v(size, 0);
	for (std::size_t i = 0; i < size; ++i) {
		std::cin >> v[i];
	}
	std::cin.ignore();
	return v;
}

std::pair<std::string, int> readPair()
{
	std::pair<std::string, int> v;
	std::cin >> v.first;
	std::cin >> v.second;
	std::cin.ignore();
	return v;
}

std::vector<std::pair<std::string, int>> readPairs(std::size_t size)
{
	std::vector<std::pair<std::string, int>> v(size);
	for (std::size_t i = 0; i < size; ++i) {
		std::cin >> v[i].first;
		std::cin >> v[i].second;
		std::cin.ignore();
	}
	return v;
}

void add(int price, std::multiset<int>& prices)
{
	prices.insert(price);
}

std::multiset<int>::iterator find_le(int price, const std::multiset<int>& prices)
{
	std::multiset<int>::iterator it = prices.upper_bound(price);
	if (it == prices.begin()) {
		return prices.end(); // error code
	}
	--it;
	return it;
}


int main(int argc, char** argv) {
	std::multiset<int> prices;
	
	const int T = readNum();
	for (std::size_t i = 0; i < T; ++i) {
		const int n = readNum();
		const std::vector<std::pair<std::string, int>> values = readPairs(n);

		std::multiset<int> prices;
		for (std::size_t j = 0; j < values.size(); ++j) {
			if (values[j].first == "sell") {
				add(values[j].second, prices);
			}
			if (values[j].first == "buy") {
				std::multiset<int>::iterator it = find_le(values[j].second, prices);
				if (it == prices.end()) {
					std::cout << "failed" << std::endl;
				}
				else {
					std::cout << *it << std::endl;
					prices.erase(it);
				}
			}
		}
	}

    return 0;
}