C++ 92.68% time 100% memory with explanation
\nclass SnapshotArray {\n    vector<vector<pair<int, int>>> history; // pair<snap_id, val>\n    int curSnap;\npublic:\n    SnapshotArray(const int& length) { //
```\nclass SnapshotArray {\n    vector<vector<pair<int, int>>> history; // pair<snap_id, val>\n    int curSnap;\npublic:\n    SnapshotArray(const int& length) { // O(length)\n        history.resize(length, {{-1, 0}});\n        curSnap = 0;\n    }\n    \n    void set(const int& index, const int& val) { // amortized O(1)\n        if (history[index].back().first < curSnap)\n            history[index].push_back({curSnap, val});\n        else\n            history[index].back().second = val;\n    }\n    \n    int snap() { // O(1)\n        return curSnap++;\n    }\n    \n    int get(const int& index, const int& snap_id) { // O(log curSnap)\n        return (upper_bound(history[index].begin(), history[index].end(), make_pair(snap_id, INT_MAX)) - 1)->second;\n    }\n};\n```\nWe store the history of snapshots. ```history[index]``` is the list of snapshots of the element at ```index```. Each elements of ```history[index]``` is a pair of the time we set the value of element[index] (```snap_id```) & ```val```. We only add an element to ```history[index]``` when there\'s at least 1 time we set the value at ```index```. There will be no new element of ```history[index]``` until we set a value for element[index] with a new ```snap_id```.\n\nEach ```history[index]``` is increasing according to ```snap_id```. To get the value of element[index] with a ```snap_id```, we can use binary search.
['Binary Search', 'C', 'C++']