Submission #882940

#	Time	Username	Problem	Language	Result	Execution time	Memory
882940		WLZ	Index (COCI21_index)	C++17	110 / 110	890 ms	65344 KiB

index

// https://oj.uz/problem/view/COCI21_index

#include <iostream>
#include <vector>
using namespace std;

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif


#include <cassert>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <string>

namespace fast_input {

    constexpr int BUF_SZ = 1 << 18;
    char buf[BUF_SZ];
    int pos = 0, len = 0;

    struct fast_reader { void tie(int *x) { (void) x; } } fcin;

    #define rd (pos == len ? (pos = 0, (!(len = (int) fread(buf, 1, BUF_SZ, stdin)) ? EOF : buf[pos++])) : buf[pos++])

    template<typename T>
    inline void read(T &x) {
        short sgn = 1; char c;
        while (!std::isdigit(c = rd)) if (c == '-') sgn = -sgn;
        x = c - '0';
        while (std::isdigit(c = rd)) { x = x * 10 + (c - '0'); }
        x *= sgn;
    }

    template<>
    inline void read<std::string>(std::string &s) {
        char c;
        s = "";
        while (!std::isspace(c = rd)) s += c;
    }

    fast_reader &getline(fast_reader &in, std::string &s) {
        s.clear(); char c;
        while ((c = rd) != '\n') s += c;
        return in;
    }

    #undef rd
} // namespace fast_input

template<typename T>
fast_input::fast_reader &operator>>(fast_input::fast_reader &in, T &x) { fast_input::read(x); return in; }

namespace fast_output {

    constexpr int BUF_SZ = 1 << 18;
    char buf[BUF_SZ];
    int pos;

    struct fast_writer {} fcout;

    void flush() { fwrite(buf, 1, pos, stdout); pos = 0; }
    void sync_with_stdio(bool b) { (void) b; assert(std::atexit(flush) == 0); }

    #define wt(c) ((pos == BUF_SZ ? flush() : (void) 0), buf[pos++] = (c))

    template<typename T>
    inline void write(const T &y) {
        T x = y;
        static char num_buf[100];
        if (x < 0) wt('-'), x = -x;
        int len = 0;
        for (; x >= 10; x /= 10) num_buf[len++] = (x % 10) + '0';
        wt(x + '0');
        while (len) wt(num_buf[--len]);
    }

    template<>
    inline void write(const char &c) { wt(c); }

    template<>
    inline void write<std::string>(const std::string &s) {
        for (const char &c : s) wt(c);
    }

    #undef wt
} // namespace fast_output

template<typename T>
fast_output::fast_writer &operator<<(fast_output::fast_writer &out, const T &x) { fast_output::write(x); return out; }

#define cin fast_input::fcin
#define ios fast_output
#define cout fast_output::fcout
#define getline fast_input::getline



#include <limits>

// Semigroup, Monoid, Group, AbelianGroup
template<typename _T>
struct addition {
    using T = _T;

    static constexpr T e = 0;
    static constexpr T op(const T &a, const T &b) { return a + b; };    
    static constexpr T inv(const T &a) { return -a; }
};

// Semigroup, Monoid
template<typename _T>
struct minimum {
    using T = _T;

    static constexpr T e = std::numeric_limits<T>::max();
    static constexpr const T &op(const T &a, const T &b) { return a < b ? a : b; }
};

// Semigroup, Monoid
template<typename _T>
struct maximum {
    using T = _T;

    static constexpr T e = std::numeric_limits<T>::min();
    static constexpr const T &op(const T &a, const T &b) { return a < b ? b : a; }
};

#include <vector>

template<typename _Sg>
class persistent_segment_tree {
    using T = typename _Sg::T;

    public:
    using value_type = T;

    persistent_segment_tree() : n(0) {}

    template<typename ...Args>
    explicit persistent_segment_tree(Args &&...args) {
        std::vector<T> a(args...);

        n = static_cast<int>(a.size());
        st.reserve(n << 1); lc.reserve(n << 1); rc.reserve(n << 1);

        root = build(0, n, a);
    }

    int original_root() const { return root; }

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

    T query(int rt, int l) const { return query(rt, l, l); }

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

    int size() const { return n; }

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

    int build(int cl, 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 static_cast<int>(st.size()) - 1;
        }
        int cm = (cl + cr) >> 1;
        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(_Sg::op(st[tmp_l], st[tmp_r]));
        return static_cast<int>(st.size()) - 1;
    }

    T query(int idx, int cl, int cr, int l, int r) const {
        if (l <= cl && cr <= r + 1) return st[idx];
        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 _Sg::op(query(lc[idx], cl, cm, l, r), query(rc[idx], cm, cr, l, r));
    }

    int update(int idx, int cl, int cr, int pos, const T &val) {
        if (cl + 1 == cr) {
            st.push_back(val); lc.push_back(0); rc.push_back(0);
            return static_cast<int>(st.size()) - 1;
        }
        int cm = (cl + cr) >> 1;
        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(_Sg::op(st[tmp_l], st[tmp_r]));
        return static_cast<int>(st.size()) - 1;
    }
};

template<typename _Sg> using persistent_segtree = persistent_segment_tree<_Sg>;
template<typename _Sg> using psegtree = persistent_segtree<_Sg>;

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

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

    psegtree< addition<int> > st(n + 1, 0);
    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; cin >> l >> r;
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (st.query(roots[mid], l, r) >= mid) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        cout << lo << '\n';
    }

    return 0;
}

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