oj.uz

Submission #753037

# Submission time Handle Problem Language Result Execution time Memory
753037 2023-06-04T13:36:26 Z I_love_Hoang_Yen Sequence (APIO23_sequence) C++17
24 / 100
 2000 ms 45996 KB 
#include "sequence.h"
#include <bits/stdc++.h>
#define SZ(s) ((int) ((s).size()))
using namespace std;

// Lazy Segment Tree, copied from AtCoder {{{
// Source: https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
// Doc: https://atcoder.github.io/ac-library/master/document_en/lazysegtree.html
//
// Notes:
// - Index of elements from 0
// - Range queries are [l, r-1]
// - composition(f, g) should return f(g())
//
// Tested:
// - https://oj.vnoi.info/problem/qmax2
// - https://oj.vnoi.info/problem/lites
// - (range set, add, mult, sum) https://oj.vnoi.info/problem/segtree_itmix
// - (range add (i-L)*A + B, sum) https://oj.vnoi.info/problem/segtree_itladder
// - https://atcoder.jp/contests/practice2/tasks/practice2_l
// - https://judge.yosupo.jp/problem/range_affine_range_sum

int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}
template<
    class S,                 // node data type
    S (*op) (S, S),          // combine 2 nodes
    S (*e) (),               // identity element
    class F,                 // lazy propagation tag
    S (*mapping) (F, S),     // apply tag F on a node
    F (*composition) (F, F), // combine 2 tags
    F (*id)()                // identity tag
>
struct LazySegTree {
    LazySegTree() : LazySegTree(0) {}
    explicit LazySegTree(int n) : LazySegTree(vector<S>(n, e())) {}
    explicit LazySegTree(const vector<S>& v) : _n((int) v.size()) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        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, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    // 0 <= p < n
    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    // Get product in range [l, r-1]
    // 0 <= l <= r <= n
    // For empty segment (l == r) -> return e()
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        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);
    }

    S all_prod() {
        return d[1];
    }

    // 0 <= p < n
    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    // Apply f on all elements in range [l, r-1]
    // 0 <= l <= r <= n
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    // 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 (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(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 (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(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<S> d;
    vector<F> lz;

    void update(int k) {
        d[k] = op(d[2*k], d[2*k+1]);
    }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2*k, lz[k]);
        all_apply(2*k+1, lz[k]);
        lz[k] = id();
    }
};
// }}}
// 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 -1000111000;
    }
};

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

using F = int;
int mapping(F f, int s) {
    return f + s;
}
F composition(F f, F g) {
    return f + g;
}
F id() { return 0; }

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

bool can(int n, int eq, const vector<int>& a, const vector<vector<int>>& ids) {
    int ln = *max_element(a.begin(), a.end());
    LazySegTree<int, MaxSegTreeOp::op, MaxSegTreeOp::e, F, mapping, composition, id> st_max(n + 1);
    LazySegTree<int, MinSegTreeOp::op, MinSegTreeOp::e, F, mapping, composition, id> st_min(n + 1);
    st_max.set(0, 0);
    st_min.set(0, 0);

    for (int median = 0; median <= ln; median++) {
        if (median == 0) {
            for (int i = 1; i <= n; ++i) {
                st_max.set(i, i);
                st_min.set(i, i);
            }
        } else {
            // greater is affected?
            for (int i : ids[median]) {
                // previously: greater = 1, now: greater = 0
                st_max.apply(i, n+1, -1);
                st_min.apply(i, n+1, -1);
            }
            // less is affected?
            for (int i : ids[median-1]) {
                // previously: less = 0, now: less = 1
                st_max.apply(i, n+1, -1);
                st_min.apply(i, n+1, -1);
            }
        }

        if (SZ(ids[median]) < eq) continue;
        for (int ix = 0, iy = eq-1; iy < SZ(ids[median]); ++ix, ++iy) {
            int x = ids[median][ix];
            int y = ids[median][iy];

            // find [l, r]:
            // - l <= x < y <= r
            // - less + eq >= greater
            // - greater + eq >= less
            // - eq >= greater - less >= -eq
            // - eq >= (greater(r) - less(r)) - (greater(l-1) - less(l-1)) >= -eq

            int max_val = st_max.prod(y, n+1) - st_min.prod(0, x);
            int min_val = st_min.prod(y, n+1) - st_max.prod(0, x);

            // [-eq, eq] and [min_val, max_val] intersects
            if (min_val <= eq && max_val >= -eq) return true;
        }
    }
    return false;
}
int sequence(int n, std::vector<int> a) {
    // ids from 1
    a.insert(a.begin(), 0);

    vector<vector<int>> ids(n + 1);
    int max_freq = 1;
    for (int i = 1; i <= n; ++i) {
        ids[a[i]].push_back(i);
        max_freq = max(max_freq, SZ(ids[a[i]]));
    }

    int left = 1, right = max_freq, res = 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (can(n, mid, a, ids)) {
            res = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    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 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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
0.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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 5 ms 460 KB Output is correct
14 Correct 6 ms 340 KB Output is correct
15 Correct 9 ms 340 KB Output is correct
16 Correct 11 ms 440 KB Output is correct
17 Correct 11 ms 440 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 12 ms 340 KB Output is correct
20 Correct 12 ms 456 KB Output is correct
21 Incorrect 17 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 611 ms 40156 KB Output is correct
3 Correct 1743 ms 40336 KB Output is correct
4 Execution timed out 2076 ms 32816 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1038 ms 45996 KB Output is correct
2 Correct 1066 ms 45884 KB Output is correct
3 Correct 417 ms 45304 KB Output is correct
4 Correct 430 ms 45224 KB Output is correct
5 Correct 736 ms 41980 KB Output is correct
6 Correct 1119 ms 42024 KB Output is correct
7 Correct 1078 ms 40880 KB Output is correct
8 Correct 795 ms 40456 KB Output is correct

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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 5 ms 460 KB Output is correct
14 Correct 6 ms 340 KB Output is correct
15 Correct 9 ms 340 KB Output is correct
16 Correct 11 ms 440 KB Output is correct
17 Correct 11 ms 440 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 12 ms 340 KB Output is correct
20 Correct 12 ms 456 KB Output is correct
21 Incorrect 17 ms 340 KB Output isn't correct
22 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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 5 ms 460 KB Output is correct
14 Correct 6 ms 340 KB Output is correct
15 Correct 9 ms 340 KB Output is correct
16 Correct 11 ms 440 KB Output is correct
17 Correct 11 ms 440 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 12 ms 340 KB Output is correct
20 Correct 12 ms 456 KB Output is correct
21 Incorrect 17 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -