Test/AtCoder/abc330_e.test.cpp

• View this file on GitHub
• Last update: 2025-08-15 21:25:19+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A
• Link: https://atcoder.jp/contests/abc330/tasks/abc330_e

Depends on

• 要素追加・削除・mex計算 (Src/DataStructure/Other/MexManager.hpp)

Code

// #define PROBLEM "https://atcoder.jp/contests/abc330/tasks/abc330_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#include "../../Src/DataStructure/Other/MexManager.hpp"

#include <iostream>

using namespace std;
int N, Q, A[200020];
int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> N >> Q;
    zawa::MexManager<int> mex;
    for (int i = 0 ; i < N ; i++) {
        std::cin >> A[i];
        mex.insert(A[i]);
    }
    while (Q--) {
        int i, x;
        cin >> i >> x;
        i--;
        mex.erase(A[i]);
        mex.insert(x);
        A[i] = x;
        cout << mex() << '\n';
    }
#else
    cout << "Hello World\n"; 
#endif
}

#line 1 "Test/AtCoder/abc330_e.test.cpp"
// #define PROBLEM "https://atcoder.jp/contests/abc330/tasks/abc330_e"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

#line 2 "Src/DataStructure/Other/MexManager.hpp"

#include <cassert>
#include <concepts>
#include <limits>
#include <utility>
#include <set>

namespace zawa {

template <std::signed_integral T>
class MexManager {
public:

    static constexpr T MAX = std::numeric_limits<T>::max();

    static constexpr T MIN = T{-1};

    MexManager() {
        m_rg.insert({MIN, MIN});
        m_rg.insert({MAX, MAX});
    }

    void insert(T v) {
        assert(MIN + 1 <= v and v <= MAX - 1);
        if (!m_set.contains(v)) {
            const T r = [&]() {
                auto it = m_rg.lower_bound({v + 1, MIN});
                if (it->first == v + 1) {
                    int res = it->second;
                    m_rg.erase(it);
                    return res;
                }
                else
                    return v;
            }();
            const T l = [&]() {
                auto it = prev(m_rg.lower_bound({v, MIN}));
                if (it->second + 1 == v) {
                    int res = it->first;
                    m_rg.erase(it);
                    return res;
                }
                else
                    return v;
            }();
            m_rg.insert({l, r});
        }
        m_set.insert(v);
    }

    void erase(T v) {
        if (!m_set.contains(v))
            return;
        m_set.erase(m_set.find(v));
        if (m_set.contains(v))
            return;
        auto it = prev(m_rg.lower_bound({v + 1, MIN}));
        const auto [l, r] = *it;
        assert(l <= v and v <= r);
        it = m_rg.erase(it);
        if (l < v) m_rg.insert({l, v - 1});
        if (v < r) m_rg.insert({v + 1, r});
    }

    T operator()() const {
        return m_rg.begin()->second + 1;
    }

private:

    std::set<std::pair<T, T>> m_rg;

    std::multiset<T> m_set;
};

} // namespace zawa
#line 5 "Test/AtCoder/abc330_e.test.cpp"

#include <iostream>

using namespace std;
int N, Q, A[200020];
int main() {
#ifdef ATCODER
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> N >> Q;
    zawa::MexManager<int> mex;
    for (int i = 0 ; i < N ; i++) {
        std::cin >> A[i];
        mex.insert(A[i]);
    }
    while (Q--) {
        int i, x;
        cin >> i >> x;
        i--;
        mex.erase(A[i]);
        mex.insert(x);
        A[i] = x;
        cout << mex() << '\n';
    }
#else
    cout << "Hello World\n"; 
#endif
}

Back to top page