leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1146.cpp (869B)

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 };