Submission #882940

# Submission time Handle Problem Language Result Execution time Memory
882940 2023-12-04T08:11:12 Z WLZ Index (COCI21_index) C++17
110 / 110
890 ms 65344 KB
// 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;
}
# Verdict Execution time Memory Grader output
1 Correct 4 ms 5980 KB Output is correct
2 Correct 3 ms 5980 KB Output is correct
3 Correct 3 ms 5980 KB Output is correct
4 Correct 3 ms 5976 KB Output is correct
5 Correct 3 ms 5980 KB Output is correct
6 Correct 3 ms 5980 KB Output is correct
7 Correct 4 ms 5980 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 3 ms 5980 KB Output is correct
10 Correct 4 ms 5976 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 5980 KB Output is correct
2 Correct 3 ms 5980 KB Output is correct
3 Correct 3 ms 5980 KB Output is correct
4 Correct 3 ms 5976 KB Output is correct
5 Correct 3 ms 5980 KB Output is correct
6 Correct 3 ms 5980 KB Output is correct
7 Correct 4 ms 5980 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 3 ms 5980 KB Output is correct
10 Correct 4 ms 5976 KB Output is correct
11 Correct 123 ms 23052 KB Output is correct
12 Correct 123 ms 23696 KB Output is correct
13 Correct 144 ms 23992 KB Output is correct
14 Correct 122 ms 24076 KB Output is correct
15 Correct 142 ms 25096 KB Output is correct
16 Correct 140 ms 22768 KB Output is correct
17 Correct 127 ms 23888 KB Output is correct
18 Correct 124 ms 24788 KB Output is correct
19 Correct 129 ms 22540 KB Output is correct
20 Correct 125 ms 23044 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 4 ms 5980 KB Output is correct
2 Correct 3 ms 5980 KB Output is correct
3 Correct 3 ms 5980 KB Output is correct
4 Correct 3 ms 5976 KB Output is correct
5 Correct 3 ms 5980 KB Output is correct
6 Correct 3 ms 5980 KB Output is correct
7 Correct 4 ms 5980 KB Output is correct
8 Correct 3 ms 5980 KB Output is correct
9 Correct 3 ms 5980 KB Output is correct
10 Correct 4 ms 5976 KB Output is correct
11 Correct 123 ms 23052 KB Output is correct
12 Correct 123 ms 23696 KB Output is correct
13 Correct 144 ms 23992 KB Output is correct
14 Correct 122 ms 24076 KB Output is correct
15 Correct 142 ms 25096 KB Output is correct
16 Correct 140 ms 22768 KB Output is correct
17 Correct 127 ms 23888 KB Output is correct
18 Correct 124 ms 24788 KB Output is correct
19 Correct 129 ms 22540 KB Output is correct
20 Correct 125 ms 23044 KB Output is correct
21 Correct 880 ms 64092 KB Output is correct
22 Correct 872 ms 64456 KB Output is correct
23 Correct 890 ms 63852 KB Output is correct
24 Correct 884 ms 64964 KB Output is correct
25 Correct 862 ms 63040 KB Output is correct
26 Correct 812 ms 63752 KB Output is correct
27 Correct 839 ms 65344 KB Output is correct
28 Correct 869 ms 64316 KB Output is correct
29 Correct 880 ms 64372 KB Output is correct
30 Correct 855 ms 63668 KB Output is correct