leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1146.cpp (869B)

      1 class SnapshotArray {
      2     vector<vector<pair<int, int>>> diffs;
      3     int id = 0;
      4 
      5   public:
      6     SnapshotArray(int length) : diffs(length, {{0, 0}}), id() {}
      7     int snap() { return id++; }
      8 
      9     void set(int index, int val) {
     10         if (diffs[index].back().first != id)
     11             diffs[index].push_back({id, val});
     12         else
     13             diffs[index].back().second = val;
     14     }
     15 
     16     int get(int index, int snap_id) {
     17         const vector<pair<int, int>> &vec = diffs[index];
     18         int low = 0, high = vec.size() - 1;
     19         while (low <= high) {
     20             int mid = low + (high - low) / 2;
     21             if (vec[mid].first == snap_id)
     22                 return vec[mid].second;
     23             else if (vec[mid].first < snap_id)
     24                 low = mid + 1;
     25             else
     26                 high = mid - 1;
     27         }
     28         return diffs[index][high].second;
     29     }
     30 };