BestHotel.cc

// https://arena.topcoder.com/#/u/practiceCode/10882/7034/7850/1/265822

#include <map>
#include <vector>

using namespace std;

struct BestHotel {
   	int numberOfDisadvantageous(vector<int> price, vector<int> quality) {
        map<int, int> bestHotels;
        int n = price.size();
        int t = 0, p, q, bq, tq;

        for (int i = 0; i < n; ++i) {
            p = price[i];
            q = quality[i];

            bq = 0;
            tq = 0;

            for (auto &pair: bestHotels) {
                if (pair.first < p) {
                    bq = pair.second >= bq ? pair.second : bq;
                }

                if (pair.first == p) {
                    tq = pair.second;
                }

                if (pair.first > p && pair.second < q + 1) {
                    pair.second = q + 1;
                    ++t;
                }
            }

            if (q > bq && q >= tq) {
                bestHotels[p] = q; 
            } else {
                ++t;
            }
        }

        return t;
    }
};