leetcode

0 class SnapshotArray {

1 vector<vector<pair<int, int>>> diffs;

2 int id = 0;

3

4 public:

5 SnapshotArray(int length) : diffs(length, {{0, 0}}), id() {}

6 int snap() { return id++; }

7

8 void set(int index, int val) {

9 if (diffs[index].back().first != id)

10 diffs[index].push_back({id, val});

11 else

12 diffs[index].back().second = val;

13 }

14

15 int get(int index, int snap_id) {

16 const vector<pair<int, int>> &vec = diffs[index];

17 int low = 0, high = vec.size() - 1;

18 while (low <= high) {

19 int mid = low + (high - low) / 2;

20 if (vec[mid].first == snap_id)

21 return vec[mid].second;

22 else if (vec[mid].first < snap_id)

23 low = mid + 1;

24 else

25 high = mid - 1;

26 }

27 return diffs[index][high].second;

28 }

29 };