oj.uz

Submission #753036

# Submission time Handle Problem Language Result Execution time Memory
753036 2023-06-04T13:35:47 Z I_love_Hoang_Yen Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 46064 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);
    for (int i = 1; i <= n; ++i) {
        ids[a[i]].push_back(i);
    }

    int left = 1, right = n, 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 1 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 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 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 17 ms 456 KB Output is correct
14 Correct 21 ms 456 KB Output is correct
15 Correct 18 ms 340 KB Output is correct
16 Correct 20 ms 440 KB Output is correct
17 Correct 16 ms 340 KB Output is correct
18 Correct 18 ms 468 KB Output is correct
19 Correct 20 ms 464 KB Output is correct
20 Correct 18 ms 456 KB Output is correct
21 Correct 19 ms 456 KB Output is correct
22 Correct 20 ms 460 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 40172 KB Time limit exceeded
3 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 2064 ms 33204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 46064 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 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 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 17 ms 456 KB Output is correct
14 Correct 21 ms 456 KB Output is correct
15 Correct 18 ms 340 KB Output is correct
16 Correct 20 ms 440 KB Output is correct
17 Correct 16 ms 340 KB Output is correct
18 Correct 18 ms 468 KB Output is correct
19 Correct 20 ms 464 KB Output is correct
20 Correct 18 ms 456 KB Output is correct
21 Correct 19 ms 456 KB Output is correct
22 Correct 20 ms 460 KB Output is correct
23 Correct 1927 ms 7884 KB Output is correct
24 Correct 1563 ms 7784 KB Output is correct
25 Correct 1896 ms 7784 KB Output is correct
26 Correct 1598 ms 6976 KB Output is correct
27 Correct 1810 ms 7084 KB Output is correct
28 Correct 1703 ms 7076 KB Output is correct
29 Correct 1455 ms 6816 KB Output is correct
30 Correct 1455 ms 6680 KB Output is correct
31 Correct 1123 ms 6612 KB Output is correct
32 Correct 1414 ms 8736 KB Output is correct
33 Correct 1252 ms 7592 KB Output is correct
34 Incorrect 1779 ms 7620 KB Output isn't correct
35 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 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 17 ms 456 KB Output is correct
14 Correct 21 ms 456 KB Output is correct
15 Correct 18 ms 340 KB Output is correct
16 Correct 20 ms 440 KB Output is correct
17 Correct 16 ms 340 KB Output is correct
18 Correct 18 ms 468 KB Output is correct
19 Correct 20 ms 464 KB Output is correct
20 Correct 18 ms 456 KB Output is correct
21 Correct 19 ms 456 KB Output is correct
22 Correct 20 ms 460 KB Output is correct
23 Execution timed out 2059 ms 40172 KB Time limit exceeded
24 Halted 0 ms 0 KB -