oj.uz

Submission #882939

# Submission time Handle Problem Language Result Execution time Memory
882939 2023-12-04T08:09:18 Z WLZ Index (COCI21_index) C++17
110 / 110
 886 ms 64848 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5980 KB Output is correct
2 Correct 3 ms 6236 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 3 ms 6236 KB Output is correct
5 Correct 3 ms 6236 KB Output is correct
6 Correct 4 ms 5980 KB Output is correct
7 Correct 4 ms 6060 KB Output is correct
8 Correct 3 ms 6096 KB Output is correct
9 Correct 3 ms 6236 KB Output is correct
10 Correct 3 ms 6236 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 6236 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 3 ms 6236 KB Output is correct
5 Correct 3 ms 6236 KB Output is correct
6 Correct 4 ms 5980 KB Output is correct
7 Correct 4 ms 6060 KB Output is correct
8 Correct 3 ms 6096 KB Output is correct
9 Correct 3 ms 6236 KB Output is correct
10 Correct 3 ms 6236 KB Output is correct
11 Correct 134 ms 19512 KB Output is correct
12 Correct 121 ms 20360 KB Output is correct
13 Correct 124 ms 19320 KB Output is correct
14 Correct 120 ms 19324 KB Output is correct
15 Correct 126 ms 19464 KB Output is correct
16 Correct 120 ms 20568 KB Output is correct
17 Correct 127 ms 19424 KB Output is correct
18 Correct 125 ms 19396 KB Output is correct
19 Correct 123 ms 20100 KB Output is correct
20 Correct 131 ms 19572 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 6236 KB Output is correct
3 Correct 3 ms 6236 KB Output is correct
4 Correct 3 ms 6236 KB Output is correct
5 Correct 3 ms 6236 KB Output is correct
6 Correct 4 ms 5980 KB Output is correct
7 Correct 4 ms 6060 KB Output is correct
8 Correct 3 ms 6096 KB Output is correct
9 Correct 3 ms 6236 KB Output is correct
10 Correct 3 ms 6236 KB Output is correct
11 Correct 134 ms 19512 KB Output is correct
12 Correct 121 ms 20360 KB Output is correct
13 Correct 124 ms 19320 KB Output is correct
14 Correct 120 ms 19324 KB Output is correct
15 Correct 126 ms 19464 KB Output is correct
16 Correct 120 ms 20568 KB Output is correct
17 Correct 127 ms 19424 KB Output is correct
18 Correct 125 ms 19396 KB Output is correct
19 Correct 123 ms 20100 KB Output is correct
20 Correct 131 ms 19572 KB Output is correct
21 Correct 803 ms 64848 KB Output is correct
22 Correct 790 ms 64488 KB Output is correct
23 Correct 845 ms 64260 KB Output is correct
24 Correct 830 ms 64272 KB Output is correct
25 Correct 825 ms 64416 KB Output is correct
26 Correct 886 ms 64048 KB Output is correct
27 Correct 850 ms 64004 KB Output is correct
28 Correct 799 ms 64092 KB Output is correct
29 Correct 822 ms 64244 KB Output is correct
30 Correct 787 ms 64424 KB Output is correct