Submission #882939

#	Time	Username	Problem	Language	Result	Execution time	Memory
882939		WLZ	Index (COCI21_index)	C++17	110 / 110	886 ms	64848 KiB

index

#include <vector>
#include <functional>
#include <numeric>

template<typename T> constexpr T my_add(T a, T b) { return a + b; }

template<typename T, auto f = my_add<T> >
class persistent_segment_tree {
    static_assert(std::is_convertible_v<decltype(f), std::function<T(T, T)> >);

    private:
    unsigned int n, root;
    std::vector<T> st;
    std::vector<unsigned int> lc, rc;

    unsigned int build(unsigned int cl, unsigned int cr, const std::vector<T> &a) {
        if (cl + 1 == cr) {
            st.push_back(a[cl]); lc.push_back(0); rc.push_back(0);
            return st.size() - 1;
        }
        unsigned int cm = (cl + cr) >> 1;
        unsigned int tmp_l = build(cl, cm, a), tmp_r = build(cm, cr, a);
        lc.push_back(tmp_l); rc.push_back(tmp_r);
        st.push_back(f(st[tmp_l], st[tmp_r]));
        return st.size() - 1;
    }

    T query(unsigned int idx, unsigned int cl, unsigned int cr, unsigned int l, unsigned int r) const {
        if (l <= cl && cr <= r) return st[idx];
        unsigned int cm = (cl + cr) >> 1;
        if (r <= cm) return query(lc[idx], cl, cm, l, r);
        if (l >= cm) return query(rc[idx], cm, cr, l, r);
        return f(query(lc[idx], cl, cm, l, r), query(rc[idx], cm, cr, l, r));
    }

    unsigned int update(unsigned int idx, unsigned int cl, unsigned int cr, unsigned int pos, const T &val) {
        if (cl + 1 == cr) {
            st.push_back(val); lc.push_back(0); rc.push_back(0);
            return st.size() - 1;
        }
        unsigned int cm = (cl + cr) >> 1;
        unsigned int tmp_l = lc[idx], tmp_r = rc[idx];
        if (pos < cm) tmp_l = update(lc[idx], cl, cm, pos, val);
        else tmp_r = update(rc[idx], cm, cr, pos, val);
        lc.push_back(tmp_l); rc.push_back(tmp_r);
        st.push_back(f(st[tmp_l], st[tmp_r]));
        return st.size() - 1;
    }

    public:
    // Note: hasn't been tested yet
    persistent_segment_tree() : n(0) {}
    
    explicit persistent_segment_tree(const std::vector<T> &a) : n(a.size()) { root = build(0, n, a); }

    // Note: hasn't been tested yet
    explicit persistent_segment_tree(size_t _n) : persistent_segment_tree(std::vector<T>(_n)) {}

    persistent_segment_tree(size_t _n, const T &x) : persistent_segment_tree(std::vector<T>(_n, x)) {}

    unsigned int original_root() const { return root; }

    T query(unsigned int idx, unsigned int l, unsigned int r) const { return query(idx, 0, n, l, r); }

    // Note: hasn't been tested yet
    T query(unsigned int idx, unsigned int l) const { return query(idx, l, l + 1); }

    unsigned int update(unsigned int idx, unsigned int pos, const T &val) { return update(idx, 0, n, pos, val); }

    // Note: hasn't been tested yet
    size_t size() const { return n; }
};

#include <iostream>
#include <map>
#include <algorithm>

const int INF = 0x3f3f3f3f;

int main() {
    std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

    int n, q; std::cin >> n >> q;
    std::vector<int> p(n + 1);
    std::vector< std::vector<int> > mp((int) 2e5 + 5);
    for (int i = 1; i <= n; i++) std::cin >> p[i], mp[p[i]].push_back(i);

    persistent_segment_tree<int> st(n + 1, 0);
    std::vector<int> roots((int) 2e5 + 5); roots[(int) 2e5 + 1] = st.original_root();

    for (int i = (int) 2e5; i >= 0; i--) {
        roots[i] = roots[i + 1];
        for (auto &idx : mp[i]) roots[i] = st.update(roots[i], idx, 1);
    }

    while (q--) {
        int l, r; std::cin >> l >> r;
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (st.query(roots[mid], l, r + 1) >= mid) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        std::cout << lo << '\n';
    }

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50