oj.uz

Submission #752963

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

// 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 sequence(int n, 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
        //
        // f1(r) >= f1(l-1)
        // f2(r) < f2(l-1)
        // max(equals[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;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 2 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 1 ms 212 KB Output is correct
8 Correct 2 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 1 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 2 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 1 ms 212 KB Output is correct
8 Correct 2 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 1 ms 212 KB Output is correct
13 Correct 606 ms 560 KB Output is correct
14 Correct 647 ms 520 KB Output is correct
15 Correct 15 ms 468 KB Output is correct
16 Correct 16 ms 468 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 705 ms 520 KB Output is correct
19 Correct 643 ms 548 KB Output is correct
20 Correct 648 ms 652 KB Output is correct
21 Correct 639 ms 520 KB Output is correct
22 Correct 633 ms 468 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 2059 ms 61416 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 531 ms 61384 KB Output is correct
3 Correct 552 ms 65716 KB Output is correct
4 Correct 539 ms 65436 KB Output is correct
5 Correct 523 ms 61392 KB Output is correct
6 Correct 468 ms 61348 KB Output is correct

Subtask #5
0.0 / 13.0

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

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 2 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 1 ms 212 KB Output is correct
8 Correct 2 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 1 ms 212 KB Output is correct
13 Correct 606 ms 560 KB Output is correct
14 Correct 647 ms 520 KB Output is correct
15 Correct 15 ms 468 KB Output is correct
16 Correct 16 ms 468 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 705 ms 520 KB Output is correct
19 Correct 643 ms 548 KB Output is correct
20 Correct 648 ms 652 KB Output is correct
21 Correct 639 ms 520 KB Output is correct
22 Correct 633 ms 468 KB Output is correct
23 Execution timed out 2071 ms 11048 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 2 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 1 ms 212 KB Output is correct
8 Correct 2 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 1 ms 212 KB Output is correct
13 Correct 606 ms 560 KB Output is correct
14 Correct 647 ms 520 KB Output is correct
15 Correct 15 ms 468 KB Output is correct
16 Correct 16 ms 468 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 705 ms 520 KB Output is correct
19 Correct 643 ms 548 KB Output is correct
20 Correct 648 ms 652 KB Output is correct
21 Correct 639 ms 520 KB Output is correct
22 Correct 633 ms 468 KB Output is correct
23 Execution timed out 2059 ms 61416 KB Time limit exceeded
24 Halted 0 ms 0 KB -