// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc273/tasks/abc273_e
// competitive-verifier: IGNORE
// AtCoder's test cases are now private.
#include "Heuristic/raw_pointer_persistent_stack.hpp"
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long Q;
cin >> Q;
RawPointerPersistentStack<int> stack;
unordered_map<int, RawPointerPersistentStack<int>> notebook;
for (int q = 0; q < Q; q++)
{
string T;
cin >> T;
if (T == "ADD")
{
int x;
cin >> x;
stack.push(x);
}
if (T == "DELETE")
{
if (!stack.empty())
{
stack.pop();
}
}
if (T == "SAVE")
{
int y;
cin >> y;
notebook[y] = stack;
}
if (T == "LOAD")
{
int z;
cin >> z;
stack = notebook[z];
}
if (!stack.empty())
{
cout << stack.top();
}
else
{
cout << -1;
}
cout << " \n"[q == Q - 1];
}
return 0;
}
#line 1 "test/Heuristic/raw_pointer_persistent_stack/abc273-e.cpp"
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc273/tasks/abc273_e
// competitive-verifier: IGNORE
// AtCoder's test cases are now private.
#line 1 "Heuristic/raw_pointer_persistent_stack.hpp"
#include <bits/stdc++.h>
using namespace std;
template <class T>
class RawPointerPersistentStack
{
protected:
struct History
{
T v;
History *previous;
int size = 1;
History(const T &v, History *previous) : v(v), previous(previous)
{
if (previous == nullptr)
{
size = 1;
return;
}
size = previous->size + 1;
}
~History()
{
delete previous;
}
};
private:
History *latest;
public:
RawPointerPersistentStack() : latest(nullptr)
{
}
RawPointerPersistentStack(History *latest) : latest(latest)
{
}
bool empty() const
{
return latest == nullptr;
}
T top() const
{
assert(!empty());
return latest->v;
}
void push(const T &v)
{
latest = new History(v, latest);
}
void pop()
{
assert(!empty());
latest = latest->previous;
}
int size() const
{
if (empty())
{
return 0;
}
return latest->size;
}
vector<T> extract_values()
{
vector<T> result;
auto now = PersistentStack(latest);
while (!now.empty())
{
result.push_back(now.top());
now.pop();
}
reverse(result.begin(), result.end());
return result;
}
};
#line 7 "test/Heuristic/raw_pointer_persistent_stack/abc273-e.cpp"
using namespace std;
int main()
{
long long Q;
cin >> Q;
RawPointerPersistentStack<int> stack;
unordered_map<int, RawPointerPersistentStack<int>> notebook;
for (int q = 0; q < Q; q++)
{
string T;
cin >> T;
if (T == "ADD")
{
int x;
cin >> x;
stack.push(x);
}
if (T == "DELETE")
{
if (!stack.empty())
{
stack.pop();
}
}
if (T == "SAVE")
{
int y;
cin >> y;
notebook[y] = stack;
}
if (T == "LOAD")
{
int z;
cin >> z;
stack = notebook[z];
}
if (!stack.empty())
{
cout << stack.top();
}
else
{
cout << -1;
}
cout << " \n"[q == Q - 1];
}
return 0;
}
test/Heuristic/raw_pointer_persistent_stack/abc273-e.cpp