fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void upsertCommodityPrice(int time, int price, unordered_map<int, int> &timeToPrice, map<int, set<int>> &priceToTimeList) {
  5.  
  6.         if(timeToPrice.find(time) != timeToPrice.end()) {
  7.  
  8.             int oldPrice = timeToPrice[time];
  9.             priceToTimeList[oldPrice].erase(time);
  10.             if (priceToTimeList[oldPrice].empty()) {
  11.                 priceToTimeList.erase(oldPrice);
  12.             }
  13.  
  14.             timeToPrice[time] = price;
  15.             priceToTimeList[price].insert(time);
  16.         } else {
  17.             timeToPrice[time] = price;
  18.             priceToTimeList[price].insert(time);
  19.         }
  20. }
  21.  
  22. int getMaxPrice(map<int, set<int>> priceToTimeList) {
  23.     return priceToTimeList.empty() ? -1 : priceToTimeList.rbegin()->first; // // Map is sorted on basis of keys in ascening order, so max entry will be last entry and we need key of last entry not value
  24. }
  25.  
  26. int main() {
  27.  
  28.  
  29.     unordered_map<int, int> timeToPrice;
  30.     map<int, set<int>> priceToTimeList;
  31.  
  32.     upsertCommodityPrice(4, 27, timeToPrice, priceToTimeList);   // 4->27                       27->(4,)
  33.     upsertCommodityPrice(6, 26, timeToPrice, priceToTimeList);   // 4->27 , 6->26               26->(6,) , 27->(4,) 
  34.     upsertCommodityPrice(9, 25, timeToPrice, priceToTimeList);   // 4->27 , 6->26, 9->25        25->(9) , 26->(6,), 27->(4,)
  35.     cout<<getMaxPrice(priceToTimeList)<<endl;         // Ans - 27
  36.  
  37.     upsertCommodityPrice(4, 24, timeToPrice, priceToTimeList);  // 4->24 , 6->26, 9->25         24->(4,) , 25->(9,) , 26->(6,)
  38.     cout<<getMaxPrice(priceToTimeList)<<endl;    // Ans - 26
  39.  
  40.     upsertCommodityPrice(6, 21, timeToPrice, priceToTimeList); // 4->24 , 6->21, 9->25           21->(6,) 24->(4,) , 25->(9,)
  41.     cout<<getMaxPrice(priceToTimeList)<<endl;       // Ans - 25
  42.  
  43.     upsertCommodityPrice(4, 21, timeToPrice, priceToTimeList); // 4->21 , 6->21, 9->25          21->(6,4,) , 25->(9,)
  44.     cout<<getMaxPrice(priceToTimeList)<<endl;  // Ans - 25
  45.  
  46.     upsertCommodityPrice(9, 15, timeToPrice, priceToTimeList); // 4->21 , 6->21, 9->15           15->(9,) , 21->(6,4,) 
  47.     cout<<getMaxPrice(priceToTimeList)<<endl;  // Ans - 21
  48.  
  49.  
  50.     // Lets say you want to print the timestamps only , when price was max , 21 is max price at time 4 and 6. So there is tie
  51.      // tie breaker - 4 should be printed first or 6 ?
  52.      // we are using set , so result is sorted first 4 then 6 
  53.      // if we want to print 4 and then 6 , then iterate from first to last 
  54.     set<int> maxTimes = priceToTimeList.rbegin()->second;          
  55.     for(auto it = maxTimes.begin(); it != maxTimes.end(); it++) {
  56.         cout<<*it<< " ";
  57.     }
  58.     cout<<endl;
  59.  
  60.      // if we want to print 6 and then 4 , then iterate from last to first , use rbegin() which points to last element
  61.      for(auto it = maxTimes.rbegin(); it != maxTimes.rend(); it++) {
  62.         cout<<*it<< " ";
  63.     }
  64.  
  65.  
  66.     return 0;
  67.  
  68. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
27
26
25
25
21
4 6 
6 4
https://ideone.com/wxVIDC
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!