/*
  Design a system that tracks the trading volume of stocks. The system must support two main operations:

     - addTrade(string stockSymbol, int volume): Updates the total
       volume traded for a given stock.
       
     - getTopK(int k): Returns the k most traded stocks (those
       with the highest volume) at the current moment.

  This is a classic “maintain dynamic top-K with frequent updates” problem. We need O(log N)
  updates and O(K) queries (where N = number of distinct stocks). Data Structures chosen

  unordered_map<string, long long>
     → stock → current total volume (O(1) average  lookup/update).
     
  set<pair<long long, string>>
     → stores {volume, stockSymbol}.

  
  Why this beats alternatives

  priority_queue alone cannot delete arbitrary elements when a stock’s volume
  changes. Sorting the map on every getTopK would be O(N log N) → too slow for large N. The
  ordered-set + hashmap pattern is the standard interview solution for “top K with updates”.

  Time & Space (what you say in the interview)
    - addTrade → O(log N) (erase + insert on set)
    - getTopK → O(K) (just walk from begin())
    - Space → O(N)
  
*/

#include <bits/stdc++.h>

using namespace std;

class TradingVolTracker
{
public:
    unordered_map<string, long long> stockToVolume;
    set<pair<long long, string>, greater<>> volumeSet;   // stores {volume, stockSymbol}

public:
    // O(log N) – one erase + one insert on the set + O(1) unordered_map operations
    void update(const pair<string,long long>& stock) {
        const string& symbol = stock.first;
        const long long& vol = stock.second; // long long to avoid
                                             // overflow on totals

        // if stock already exists, remove old entry from ordered set
        if (stockToVolume.count(symbol))
        {
            long long oldVol = stockToVolume[symbol];
            volumeSet.erase({oldVol, symbol});
        }

        stockToVolume[symbol] += vol;
        
        // Insert new ordered entry
        volumeSet.insert({stockToVolume[symbol], symbol});
    }

    /**
     * Returns the k most traded stocks (highest volume first).
     * If k > number of stocks, returns all stocks.
     * Ties are broken by stock symbol (lexicographically).
     */

    vector<string> getTopK(int k) {
        vector<string> result;
        if (k <= 0) return result;

        auto it = volumeSet.begin();
        for (int i = 0; i < k && it != volumeSet.end(); ++i, ++it) {
            result.push_back(it->second);
        }
        return result;
    }
};


int main(void)
{
    vector<tuple<vector<pair<string,long long>>, int>> testCases
        {
            // input - vector<pair>
            {{ {"AAPL", 1000}, {"TSLA", 5000}, {"QCOM", 2000}, {"NVDA", 7000},
               {"AMZN", 9000}, {"NFLX", 11000}, {"MSFT", 13000}, {"GOOGL", 15000} 
                },
             // output - top K
             {3}},
            {{ {"AAPL", 16000}
                },
             {3}},
        };
    
    TradingVolTracker tracker;
    for (auto& tc: testCases)
    {
        for (const auto& stock: get<0>(tc))
            tracker.update(stock);
        
        
        vector<string> stocks = tracker.getTopK(get<1>(tc));
        for (const auto& i: stocks)
            cout << i << ", ";
        cout << endl << "---------------" << endl;        
    }

    return 0;
}