oj.uz

Submission #752986

# Submission time Handle Problem Language Result Execution time Memory
752986 2023-06-04T11:50:34 Z I_love_Hoang_Yen Sequence (APIO23_sequence) C++17
47 / 100
 2000 ms 61552 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]) {
                // l = i + 1
                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));
                }
                // 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 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 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 224 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 1 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 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 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 224 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 1 ms 212 KB Output is correct
12 Correct 2 ms 212 KB Output is correct
13 Correct 507 ms 552 KB Output is correct
14 Correct 512 ms 648 KB Output is correct
15 Correct 12 ms 468 KB Output is correct
16 Correct 15 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 552 ms 552 KB Output is correct
20 Correct 530 ms 588 KB Output is correct
21 Correct 488 ms 652 KB Output is correct
22 Correct 479 ms 532 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 168 ms 31660 KB Output is correct
3 Correct 183 ms 31644 KB Output is correct
4 Correct 35 ms 6104 KB Output is correct
5 Correct 174 ms 29104 KB Output is correct
6 Correct 147 ms 29308 KB Output is correct
7 Correct 41 ms 6096 KB Output is correct
8 Correct 48 ms 6100 KB Output is correct
9 Correct 35 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 438 ms 61552 KB Output is correct
3 Correct 408 ms 61348 KB Output is correct
4 Correct 447 ms 61328 KB Output is correct
5 Correct 438 ms 61364 KB Output is correct
6 Correct 394 ms 61448 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 61520 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 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 224 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 1 ms 212 KB Output is correct
12 Correct 2 ms 212 KB Output is correct
13 Correct 507 ms 552 KB Output is correct
14 Correct 512 ms 648 KB Output is correct
15 Correct 12 ms 468 KB Output is correct
16 Correct 15 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 552 ms 552 KB Output is correct
20 Correct 530 ms 588 KB Output is correct
21 Correct 488 ms 652 KB Output is correct
22 Correct 479 ms 532 KB Output is correct
23 Execution timed out 2033 ms 10984 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 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 224 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 1 ms 212 KB Output is correct
12 Correct 2 ms 212 KB Output is correct
13 Correct 507 ms 552 KB Output is correct
14 Correct 512 ms 648 KB Output is correct
15 Correct 12 ms 468 KB Output is correct
16 Correct 15 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 552 ms 552 KB Output is correct
20 Correct 530 ms 588 KB Output is correct
21 Correct 488 ms 652 KB Output is correct
22 Correct 479 ms 532 KB Output is correct
23 Correct 168 ms 31660 KB Output is correct
24 Correct 183 ms 31644 KB Output is correct
25 Correct 35 ms 6104 KB Output is correct
26 Correct 174 ms 29104 KB Output is correct
27 Correct 147 ms 29308 KB Output is correct
28 Correct 41 ms 6096 KB Output is correct
29 Correct 48 ms 6100 KB Output is correct
30 Correct 35 ms 6100 KB Output is correct
31 Correct 438 ms 61552 KB Output is correct
32 Correct 408 ms 61348 KB Output is correct
33 Correct 447 ms 61328 KB Output is correct
34 Correct 438 ms 61364 KB Output is correct
35 Correct 394 ms 61448 KB Output is correct
36 Execution timed out 2063 ms 61520 KB Time limit exceeded
37 Halted 0 ms 0 KB -