cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: Test/CF/CF1054-G.test.cpp

Depends on

Code

// #define PROBLEM "https://codeforces.com/contest/2149/problem/G"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * Codeforces Round 1054 (Div. 3) G - Buratsuta 3
 * https://codeforces.com/contest/2149/submission/340565209
 */

#include "../../Src/Sequence/CompressedSequence.hpp"
#include "../../Src/DataStructure/Mo/RollbackMo.hpp"

#include <iostream>
#include <vector>
using namespace std;
using namespace zawa;
struct Query {
    usize l, r;
};
struct Data {
    int top1 = -1, top2 = -1, last_op = -1;
};
void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int& a : A)
        cin >> a;
    vector<Query> q(Q);
    for (auto& [l, r] : q) {
        cin >> l >> r;
        l--;
    }
    CompressedSequence comp{A};
    for (int i = 0 ; i < N ; i++)
        A[i] = comp.map(i);
    vector<int> cnt(ssize(comp));
    auto add = [&](int i, Data d) {
        cnt[A[i]]++; 
        if (d.top1 == A[i])
            ;
        else if (d.top2 == A[i]) {
            if (cnt[d.top1] < cnt[d.top2])
                swap(d.top1, d.top2);
        }
        else if (d.top1 == -1 or cnt[A[i]] > cnt[d.top1]) {
            d.top2 = d.top1;
            d.top1 = A[i];
        }
        else if (d.top2 == -1 or cnt[A[i]] > cnt[d.top2])
            d.top2 = A[i];
        d.last_op = A[i];
        return d;
    };
    auto rollback = [&](const Data& d) {
        cnt[d.last_op]--;
    };
    auto eval = [&](int i, const Data& d) {
        vector<int> res;
        const int len = q[i].r - q[i].l;
        if (d.top1 != -1 and cnt[d.top1] * 3 > len)
            res.push_back(comp.inverse(d.top1));
        if (d.top2 != -1 and cnt[d.top2] * 3 > len)
            res.push_back(comp.inverse(d.top2));
        if (ssize(res) == 2 and res[0] > res[1])
            swap(res[0], res[1]);
        if (res.empty())
            res.push_back(-1);
        return res;
    };
    for (const vector<int>& ans : RollbackMo<Query, Data, decltype(add), decltype(rollback), decltype(eval)>(q, add, add, rollback, eval))
        for (int i = 0 ; i < ssize(ans) ; i++)
            cout << ans[i] << (i + 1 == ssize(ans) ? '\n' : ' ');
}
int main() {
#ifdef ONLINE_JUDGE
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--)
        solve();
#else
    cout << "Hello World\n";
#endif
}
#line 1 "Test/CF/CF1054-G.test.cpp"
// #define PROBLEM "https://codeforces.com/contest/2149/problem/G"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/1/ITP1_1_A"

/*
 * Codeforces Round 1054 (Div. 3) G - Buratsuta 3
 * https://codeforces.com/contest/2149/submission/340565209
 */

#line 2 "Src/Sequence/CompressedSequence.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Sequence/CompressedSequence.hpp"

#include <vector>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <limits>

namespace zawa {

template <class T>
class CompressedSequence {
public:

    static constexpr u32 NotFound = std::numeric_limits<u32>::max();

    CompressedSequence() = default;

    template <class InputIterator>
    CompressedSequence(InputIterator first, InputIterator last) : comped_(first, last), f_{} {
        std::sort(comped_.begin(), comped_.end());
        comped_.erase(std::unique(comped_.begin(), comped_.end()), comped_.end());
        comped_.shrink_to_fit();
        f_.reserve(std::distance(first, last));
        for (auto it{first} ; it != last ; it++) {
            f_.emplace_back(std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), *it)));
        }
    }

    CompressedSequence(const std::vector<T>& A) : CompressedSequence(A.begin(), A.end()) {}

    inline usize size() const noexcept {
        return comped_.size();
    }

    u32 operator[](const T& v) const {
        return std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
    }

    u32 upper_bound(const T& v) const {
        return std::distance(comped_.begin(), std::upper_bound(comped_.begin(), comped_.end(), v));
    }

    u32 find(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i == comped_.size() or comped_[i] != v ? NotFound : i;
    }

    bool contains(const T& v) const {
        u32 i = std::distance(comped_.begin(), std::lower_bound(comped_.begin(), comped_.end(), v));
        return i < comped_.size() and comped_[i] == v;
    }

    u32 at(const T& v) const {
        u32 res = find(v);
        assert(res != NotFound);
        return res;
    }

    inline u32 map(u32 i) const noexcept {
        assert(i < f_.size());
        return f_[i];
    }

    inline T inverse(u32 i) const noexcept {
        assert(i < size());
        return comped_[i];
    }

    inline std::vector<T> comped() const noexcept {
        return comped_;
    }

private:

    std::vector<T> comped_;

    std::vector<u32> f_;

};

} // namespace zawa
#line 2 "Src/DataStructure/Mo/RollbackMo.hpp"

#line 4 "Src/DataStructure/Mo/RollbackMo.hpp"

#line 7 "Src/DataStructure/Mo/RollbackMo.hpp"
#include <concepts>
#line 9 "Src/DataStructure/Mo/RollbackMo.hpp"
#include <utility>
#line 11 "Src/DataStructure/Mo/RollbackMo.hpp"

namespace zawa {

template <class T, class RBT, class Add, class Rollback, class Eval>
std::vector<typename std::invoke_result_t<Eval, usize, const RBT&>> RollbackMo(const std::vector<T>& qs, Add addL, Add addR, Rollback rollback, Eval eval) {
    const usize n = [&]() {
        usize mx = 0;
        for (usize i = 0 ; i < qs.size() ; i++) {
            assert(qs[i].l <= qs[i].r);
            mx = std::max<usize>(mx, qs[i].r);
        }
        return mx;
    }();
    const usize SQ = [&]() {
        usize i = 1;
        while (i * i < n)
            i++;
        return i;
    }();
    std::vector<std::vector<std::pair<usize, usize>>> rs((n + SQ - 1) / SQ);
    std::vector<typename std::invoke_result_t<Eval, usize, const RBT&>> res(qs.size());
    std::vector<RBT> history;
    history.emplace_back();
    for (usize i = 0 ; i < qs.size() ; i++) {
        if (qs[i].r - qs[i].l <= SQ) {
            for (usize j = qs[i].l ; j < qs[i].r ; j++)
                history.push_back(addR(j, history.back()));
            res[i] = eval(i, history.back());
            for (usize j = qs[i].l ; j < qs[i].r ; j++) {
                rollback(history.back());
                history.pop_back();
            }
        }
        else
            rs[qs[i].l / SQ].emplace_back(qs[i].r, i);
    }
    for (usize i = 0 ; i < rs.size() ; i++)
        if (rs[i].size()) {
            std::sort(rs[i].begin(), rs[i].end());
            const usize L = (i + 1) * SQ;
            usize R = L;
            for (auto [r, idx] : rs[i]) {
                while (R < r)
                    history.push_back(addR(R++, history.back()));
                for (usize j = L ; j > qs[idx].l ; )
                    history.push_back(addL(--j, history.back()));
                res[idx] = eval(idx, history.back());
                for (usize j = L ; j > qs[idx].l ; j--) {
                    rollback(history.back());
                    history.pop_back();
                }
            }
            for (usize j = L ; j < R ; j++) {
                rollback(history.back());
                history.pop_back();
            }
        }
    return res;
}

} // namespace zawa
#line 11 "Test/CF/CF1054-G.test.cpp"

#include <iostream>
#line 14 "Test/CF/CF1054-G.test.cpp"
using namespace std;
using namespace zawa;
struct Query {
    usize l, r;
};
struct Data {
    int top1 = -1, top2 = -1, last_op = -1;
};
void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int& a : A)
        cin >> a;
    vector<Query> q(Q);
    for (auto& [l, r] : q) {
        cin >> l >> r;
        l--;
    }
    CompressedSequence comp{A};
    for (int i = 0 ; i < N ; i++)
        A[i] = comp.map(i);
    vector<int> cnt(ssize(comp));
    auto add = [&](int i, Data d) {
        cnt[A[i]]++; 
        if (d.top1 == A[i])
            ;
        else if (d.top2 == A[i]) {
            if (cnt[d.top1] < cnt[d.top2])
                swap(d.top1, d.top2);
        }
        else if (d.top1 == -1 or cnt[A[i]] > cnt[d.top1]) {
            d.top2 = d.top1;
            d.top1 = A[i];
        }
        else if (d.top2 == -1 or cnt[A[i]] > cnt[d.top2])
            d.top2 = A[i];
        d.last_op = A[i];
        return d;
    };
    auto rollback = [&](const Data& d) {
        cnt[d.last_op]--;
    };
    auto eval = [&](int i, const Data& d) {
        vector<int> res;
        const int len = q[i].r - q[i].l;
        if (d.top1 != -1 and cnt[d.top1] * 3 > len)
            res.push_back(comp.inverse(d.top1));
        if (d.top2 != -1 and cnt[d.top2] * 3 > len)
            res.push_back(comp.inverse(d.top2));
        if (ssize(res) == 2 and res[0] > res[1])
            swap(res[0], res[1]);
        if (res.empty())
            res.push_back(-1);
        return res;
    };
    for (const vector<int>& ans : RollbackMo<Query, Data, decltype(add), decltype(rollback), decltype(eval)>(q, add, add, rollback, eval))
        for (int i = 0 ; i < ssize(ans) ; i++)
            cout << ans[i] << (i + 1 == ssize(ans) ? '\n' : ' ');
}
int main() {
#ifdef ONLINE_JUDGE
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--)
        solve();
#else
    cout << "Hello World\n";
#endif
}
Back to top page