1
class SnapshotArray {
2
  int timestamp;
3
  unordered_map<int, vector<int>> toSnaps, toValues;
4

5
 public:
6
  SnapshotArray(int length) {
7
    timestamp = 0;
8
  }
9

10
  void set(int index, int val) {
11
    if (toSnaps.count(index) == 0) {
12
      // After lower_bound, prevent returning negative lo
13
      toSnaps[index].push_back(-1);
14
      // 0 means not found
15
      toValues[index].push_back(0);
16
    }
17
    // same timestamp -> just update value
18
    if (toSnaps[index].back() == timestamp) {
19
      toValues[index].back() = val;
20
    }
21
    // not -> add timestamp and value
22
    else {
23
      toSnaps[index].push_back(timestamp);
24
      toValues[index].push_back(val);
25
    }
26
  }
27

28
  int snap() {
29
    return timestamp++;
30
  }
31

32
  int get(int index, int snap_id) {
33
    // check whether index exists or not
34
    if (toSnaps.count(index) == 0) return 0;
35
    auto &snaps = toSnaps[index];
36
    int lo = 0, hi = snaps.size() - 1;
37
    while (lo < hi) {
38
      int m = lo + (hi - lo) / 2;
39
      if (snaps[m] >= snap_id)
40
        hi = m;
41
      else
42
        lo = m + 1;
43
    }
44
    // lower bound can be larger than target
45
    if (snaps[lo] > snap_id) lo--;
46
    // if lo is negative, then ther is no value of index at lo time
47
    // if (lo < 0) return 0;
48
    return toValues[index][lo];
49
  }
50
};
51

52
/**
53
 * Your SnapshotArray object will be instantiated and called as such:
54
 * SnapshotArray* obj = new SnapshotArray(length);
55
 * obj->set(index,val);
56
 * int param_2 = obj->snap();
57
 * int param_3 = obj->get(index,snap_id);
58
 */