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

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.0 / 20.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

Subtask #2
40.0 / 40.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
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

Subtask #3
50.0 / 50.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
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

Submission #882940

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 40.0 / 40.0

Subtask #3 50.0 / 50.0

Subtask #1
20.0 / 20.0

Subtask #2
40.0 / 40.0

Subtask #3
50.0 / 50.0