leetcode

commit f02c3256e18f4c335156c94319914a4548989115
parent 07e2b532294e6b2ae9d493c79c5cac43dd05efc5
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 11 Jun 2023 15:38:05 +0200

Daily Problem

Diffstat:
A
Problems/1146.cpp
 | 
35
+++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 36 insertions(+), 0 deletions(-)
diff --git a/Problems/1146.cpp b/Problems/1146.cpp
@@ -0,0 +1,35 @@
+class SnapshotArray {
+  vector<vector<pair<int, int>>> diffs;
+  int id = 0;
+
+public:
+  SnapshotArray(int length)
+      : diffs(length,
+              {
+                  {0, 0}
+  }),
+        id() {}
+  int snap() { return id++; }
+
+  void set(int index, int val) {
+    if (diffs[index].back().first != id)
+      diffs[index].push_back({id, val});
+    else
+      diffs[index].back().second = val;
+  }
+
+  int get(int index, int snap_id) {
+    const vector<pair<int, int>> &vec = diffs[index];
+    int low = 0, high = vec.size() - 1;
+    while (low <= high) {
+      int mid = low + (high - low) / 2;
+      if (vec[mid].first == snap_id)
+        return vec[mid].second;
+      else if (vec[mid].first < snap_id)
+        low = mid + 1;
+      else
+        high = mid - 1;
+    }
+    return diffs[index][high].second;
+  }
+};
diff --git a/README.md b/README.md
@@ -420,6 +420,7 @@ for solving problems.
 |  1137  |    Easy    | [N-th Tribonacci Number](Problems/1137.cpp)                                                      |
 |  1140  |   Medium   | [Stone Game II](Problems/1140.cpp)                                                               |
 |  1143  |   Medium   | [Longest Common Subsequence](Problems/1143.cpp)                                                  |
+|  1146  |   Medium   | [Snapshot Array](Problems/1146.cpp)                                                              |
 |  1162  |   Medium   | [As Far from Land as Possible](Problems/1162.cpp)                                                |
 |  1202  |   Medium   | [Smallest String With Swaps](Problems/1202.cpp)                                                  |
 |  1209  |   Medium   | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp)                                 |