test/DataStructure/persistent_stack/abc273-e.cpp

View this file on GitHub
Last update: 2025-03-23 20:36:27+09:00
Problem: https://atcoder.jp/contests/abc273/tasks/abc273_e

Depends on

永続スタック (DataStructure/persistent_stack.hpp)

Code

// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc273/tasks/abc273_e
// competitive-verifier: IGNORE
// AtCoder's test cases are now private.

#include "DataStructure/persistent_stack.hpp"
#include <bits/stdc++.h>

using namespace std;

int main()
{

    long long Q;
    cin >> Q;

    PersistentStack<int> stack;
    unordered_map<int, PersistentStack<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/DataStructure/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 "DataStructure/persistent_stack.hpp"
#include <bits/stdc++.h>

using namespace std;

template <class T>
class PersistentStack
{
protected:
    struct History
    {
        T v;
        shared_ptr<History> previous;
        int size = 1;
        History(const T &v, shared_ptr<History> previous) : v(v), previous(previous)
        {
            if (previous == nullptr)
            {
                size = 1;
                return;
            }

            size = previous->size + 1;
        }
    };

private:
    shared_ptr<History> latest;

public:
    PersistentStack() : latest(nullptr)
    {
    }

    PersistentStack(shared_ptr<History> latest) : latest(latest)
    {
    }

    bool empty() const
    {
        return latest == nullptr;
    }

    T top() const
    {
        assert(!empty());
        return latest->v;
    }

    void push(const T &v)
    {
        latest = make_shared<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/DataStructure/persistent_stack/abc273-e.cpp"

using namespace std;

int main()
{

    long long Q;
    cin >> Q;

    PersistentStack<int> stack;
    unordered_map<int, PersistentStack<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;
}