oj.uz

Submission #752982

# Submission time Handle Problem Language Result Execution time Memory
752982 2023-06-04T11:43:41 Z I_love_Hoang_Yen Sequence (APIO23_sequence) C++17
47 / 100
 2000 ms 61468 KB 
#include "sequence.h"
#include <bits/stdc++.h>
#define SZ(s) ((int) ((s).size()))
using namespace std;

bool is_sub_3(const std::vector<int> a) {
    auto mit = max_element(a.begin(), a.end());
    return std::is_sorted(a.begin(), mit)
        && std::is_sorted(mit, a.end(), std::greater<int>());
}

int len(const std::pair<int,int>& p) {
    return p.second - p.first + 1;
}
bool can_be_median(int cnt_less, int cnt_equal, int cnt_greater) {
    return cnt_equal + cnt_less >= cnt_greater;
}

int sub3(const vector<int>& a) {
    int n = SZ(a);
    unordered_map<int, vector<pair<int,int>>> pos;
    int l = 0;
    while (l < n) {
        int r = l;
        while (r < n && a[l] == a[r]) ++r;
        pos[a[l]].emplace_back(l, r-1);
        l = r;
    }
    int res = 0;
    for (const auto& [val, lrs] : pos) {
        // only 1 segment
        for (const auto& lr : lrs) res = max(res, len(lr));

        // 2 segments
        if (SZ(lrs) < 2) continue;
        assert(SZ(lrs) == 2);
        int cnt_equal = len(lrs[0]) + len(lrs[1]);
        int cnt_greater = len({lrs[0].second + 1, lrs[1].first - 1});
        int cnt_less = len({0, lrs[0].first - 1}) + len({lrs[1].second + 1, n-1});
        if (can_be_median(cnt_less, cnt_equal, cnt_greater)) {
            res = max(res, cnt_equal);
        }
    }
    return res;
}

// SegTree, copied from AtCoder library {{{
// AtCoder doc: https://atcoder.github.io/ac-library/master/document_en/segtree.html
//
// Notes:
// - Index of elements from 0 -> n-1
// - Range queries are [l, r-1]
//
// Tested:
// - (binary search) https://atcoder.jp/contests/practice2/tasks/practice2_j
// - https://oj.vnoi.info/problem/gss
// - https://oj.vnoi.info/problem/nklineup
// - (max_right & min_left for delete position queries) https://oj.vnoi.info/problem/segtree_itstr
// - https://judge.yosupo.jp/problem/point_add_range_sum
// - https://judge.yosupo.jp/problem/point_set_range_composite
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

template<
    class T,  // data type for nodes
    T (*op) (T, T),  // operator to combine 2 nodes
    T (*e)() // identity element
>
struct SegTree {
    SegTree() : SegTree(0) {}
    explicit SegTree(int n) : SegTree(vector<T> (n, e())) {}
    explicit SegTree(const vector<T>& v) : _n((int) v.size()) {
        log = ceil_pow2(_n);
        size = 1<<log;
        d = vector<T> (2*size, e());

        for (int i = 0; i < _n; i++) d[size+i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    // 0 <= p < n
    void set(int p, T x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    // 0 <= p < n
    T get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    // Get product in range [l, r-1]
    // 0 <= l <= r <= n
    // For empty segment (l == r) -> return e()
    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        T sml = e(), smr = e();
        l += size;
        r += size;
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    T all_prod() const {
        return d[1];
    }

    // Binary search on SegTree to find largest r:
    //    f(op(a[l] .. a[r-1])) = true   (assuming empty array is always true)
    //    f(op(a[l] .. a[r])) = false    (assuming op(..., a[n]), which is out of bound, is always false)
    template <bool (*f)(T)> int max_right(int l) const {
        return max_right(l, [](T x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        T sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    // Binary search on SegTree to find smallest l:
    //    f(op(a[l] .. a[r-1])) = true      (assuming empty array is always true)
    //    f(op(a[l-1] .. a[r-1])) = false   (assuming op(a[-1], ..), which is out of bound, is always false)
    template <bool (*f)(T)> int min_left(int r) const {
        return min_left(r, [](T x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        T sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

private:
    int _n, size, log;
    vector<T> d;

    void update(int k) {
        d[k] = op(d[2*k], d[2*k+1]);
    }
};
// }}}
// SegTree examples {{{
// Examples: Commonly used SegTree ops: max / min / sum
struct MaxSegTreeOp {
    static int op(int x, int y) {
        return max(x, y);
    }
    static int e() {
        return INT_MIN;
    }
};

struct MinSegTreeOp {
    static int op(int x, int y) {
        return min(x, y);
    }
    static int e() {
        return INT_MAX;
    }
};

struct SumSegTreeOp {
    static long long op(long long x, long long y) {
        return x + y;
    }
    static long long e() {
        return 0;
    }
};

// using STMax = SegTree<int, MaxSegTreeOp::op, MaxSegTreeOp::e>;
// using STMin = SegTree<int, MinSegTreeOp::op, MinSegTreeOp::e>;
// using STSum = SegTree<int, SumSegTreeOp::op, SumSegTreeOp::e>;
// }}}

int sub4(int n, const std::vector<int>& a) {
    int res = 0;
    int ln = *max_element(a.begin(), a.end());
    for (int median = 0; median <= ln; ++median) {
        vector<int> cnt_less(n, 0);
        vector<int> cnt_equal(n, 0);
        vector<int> cnt_greater(n, 0);
        for (int i = 0; i < n; ++i) {
            cnt_less[i] = a[i] < median;
            cnt_equal[i] = a[i] == median;
            cnt_greater[i] = a[i] > median;
        }
        std::partial_sum(cnt_less.begin(), cnt_less.end(), cnt_less.begin());
        std::partial_sum(cnt_equal.begin(), cnt_equal.end(), cnt_equal.begin());
        std::partial_sum(cnt_greater.begin(), cnt_greater.end(), cnt_greater.begin());

        //    cnt_less[r]   + cnt_equal[r]   - cnt_greater[r]
        // >= cnt_less[l-1] + cnt_equal[l-1] - cnt_greater[l-1]
        //
        //    cnt_less[r]   - cnt_equal[r]   - cnt_greater[r]
        //  < cnt_less[l-1] - cnt_equal[l-1] - cnt_greater[l-1]
        //
        //  l < r
        vector<vector<pair<int,int>>> f1_at(n*2 + 1);
        for (int i = n-1; i >= 0; --i) {
            // add n so that everything >= 0
            int f1 = cnt_less[i] + cnt_equal[i] - cnt_greater[i] + n;
            int f2 = cnt_less[i] - cnt_equal[i] - cnt_greater[i] + n;
            f1_at[f1].emplace_back(i, f2);
        }
        f1_at[n].emplace_back(-1, n);

        SegTree<int, MaxSegTreeOp::op, MaxSegTreeOp::e> st(2*n + 1);
        for (int f1 = 2*n; f1 >= 0; --f1) {
            // f1(r) > f1(l-1) && f2(r) <= f2(l-1)
            for (const auto& [i, f2] : f1_at[f1]) {
                int max_r = st.prod(0, f2 + 1);
                if (max_r > i) {
                    res = max(res, cnt_equal[max_r] - (i >= 0 ? cnt_equal[i] : 0));
                }
            }
            // f1(r) >= f1(l-1) && f2(r) < f2(l-1)
            for (const auto& [i, f2] : f1_at[f1]) {
                // l = i + 1
                int max_r = st.prod(0, f2);
                if (max_r > i) {
                    res = max(res, cnt_equal[max_r] - (i >= 0 ? cnt_equal[i] : 0));
                }
                // r = i
                st.set(f2, max(st.get(f2), i));
            }
        }
    }
    return res;
}

int sequence(int n, std::vector<int> a) {
    if (is_sub_3(a)) return sub3(a);
    return sub4(n, a);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 2 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 2 ms 212 KB Output is correct
13 Correct 608 ms 520 KB Output is correct
14 Correct 627 ms 532 KB Output is correct
15 Correct 15 ms 468 KB Output is correct
16 Correct 15 ms 536 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 654 ms 552 KB Output is correct
20 Correct 668 ms 524 KB Output is correct
21 Correct 674 ms 656 KB Output is correct
22 Correct 673 ms 528 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 183 ms 31600 KB Output is correct
3 Correct 192 ms 31648 KB Output is correct
4 Correct 40 ms 6088 KB Output is correct
5 Correct 165 ms 29076 KB Output is correct
6 Correct 140 ms 29068 KB Output is correct
7 Correct 39 ms 6108 KB Output is correct
8 Correct 44 ms 6088 KB Output is correct
9 Correct 43 ms 6100 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 639 ms 61360 KB Output is correct
3 Correct 554 ms 61344 KB Output is correct
4 Correct 644 ms 61344 KB Output is correct
5 Correct 588 ms 61316 KB Output is correct
6 Correct 489 ms 61340 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 61468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 2 ms 212 KB Output is correct
13 Correct 608 ms 520 KB Output is correct
14 Correct 627 ms 532 KB Output is correct
15 Correct 15 ms 468 KB Output is correct
16 Correct 15 ms 536 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 654 ms 552 KB Output is correct
20 Correct 668 ms 524 KB Output is correct
21 Correct 674 ms 656 KB Output is correct
22 Correct 673 ms 528 KB Output is correct
23 Execution timed out 2062 ms 10860 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 2 ms 212 KB Output is correct
12 Correct 2 ms 212 KB Output is correct
13 Correct 608 ms 520 KB Output is correct
14 Correct 627 ms 532 KB Output is correct
15 Correct 15 ms 468 KB Output is correct
16 Correct 15 ms 536 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 654 ms 552 KB Output is correct
20 Correct 668 ms 524 KB Output is correct
21 Correct 674 ms 656 KB Output is correct
22 Correct 673 ms 528 KB Output is correct
23 Correct 183 ms 31600 KB Output is correct
24 Correct 192 ms 31648 KB Output is correct
25 Correct 40 ms 6088 KB Output is correct
26 Correct 165 ms 29076 KB Output is correct
27 Correct 140 ms 29068 KB Output is correct
28 Correct 39 ms 6108 KB Output is correct
29 Correct 44 ms 6088 KB Output is correct
30 Correct 43 ms 6100 KB Output is correct
31 Correct 639 ms 61360 KB Output is correct
32 Correct 554 ms 61344 KB Output is correct
33 Correct 644 ms 61344 KB Output is correct
34 Correct 588 ms 61316 KB Output is correct
35 Correct 489 ms 61340 KB Output is correct
36 Execution timed out 2067 ms 61468 KB Time limit exceeded
37 Halted 0 ms 0 KB -