1
class TimeMap {
2
 public:
3
  map<string, vector<pair<int, string>>> mp;
4
  string Max;
5
  TimeMap() {
6
    Max = "";
7
  }
8

9
  void set(string key, string value, int timestamp) {
10
    mp[key].push_back(make_pair(timestamp, value));
11
    Max = max(Max, value);
12
  }
13

14
  string get(string key, int timestamp) {
15
    pair<int, string> p = make_pair(timestamp, Max);
16
    int l = upper_bound(mp[key].begin(), mp[key].end(), p) - mp[key].begin();
17
    if (l == 0) {
18
      return "";
19
    }
20
    return mp[key][l - 1].second;
21
  }
22
};
23

24
/**
25
 * Your TimeMap object will be instantiated and called as such:
26
 * TimeMap* obj = new TimeMap();
27
 * obj->set(key,value,timestamp);
28
 * string param_2 = obj->get(key,timestamp);
29
 */