제출 #1208122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208122		gatapdev	K개의 묶음 (IZhO14_blocks)	C++20	0 / 100	1 ms	328 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;

// Segment-tree-beats: support range_max_assign (chmax) and range_min query
struct Beats {
    struct Node { ll mn, snd_mn, cnt_mn, lazy_add; };
    int n;
    vector<Node> st;

    Beats(int _n): n(_n), st(4*n) {}

    void apply_min(int p, ll x) {
        if (st[p].mn >= x) return;
        st[p].mn = x;
        // lazy_add not changed, we only push upward
    }

    void push(int p) {
        for (int k: {p<<1, p<<1|1}) {
            apply_min(k, st[p].mn);
        }
    }

    void pull(int p) {
        auto &l = st[p<<1], &r = st[p<<1|1], &u = st[p];
        if (l.mn < r.mn) {
            u.mn = l.mn;
            u.cnt_mn = l.cnt_mn;
            u.snd_mn = min(l.snd_mn, r.mn);
        } else if (r.mn < l.mn) {
            u.mn = r.mn;
            u.cnt_mn = r.cnt_mn;
            u.snd_mn = min(r.snd_mn, l.mn);
        } else {
            u.mn = l.mn;
            u.cnt_mn = l.cnt_mn + r.cnt_mn;
            u.snd_mn = min(l.snd_mn, r.snd_mn);
        }
    }

    void build(int p, int l, int r, const vector<ll>& base) {
        if (l == r) {
            st[p].mn = base[l];
            st[p].snd_mn = INF;
            st[p].cnt_mn = 1;
            return;
        }
        int m = (l+r)/2;
        build(p<<1, l, m, base);
        build(p<<1|1, m+1, r, base);
        pull(p);
    }

    // set all values in [i,j] to at least x
    void range_chmax(int p, int l, int r, int i, int j, ll x) {
        if (i>r || j<l || st[p].mn >= x) return;
        if (i<=l && r<=j && st[p].snd_mn > x) {
            apply_min(p, x);
            return;
        }
        push(p);
        int m = (l+r)/2;
        range_chmax(p<<1, l, m, i, j, x);
        range_chmax(p<<1|1, m+1, r, i, j, x);
        pull(p);
    }

    ll range_min(int p, int l, int r, int i, int j) {
        if (i>r || j<l) return INF;
        if (i<=l && r<=j) return st[p].mn;
        push(p);
        int m = (l+r)/2;
        return min(range_min(p<<1, l, m, i, j),
                   range_min(p<<1|1, m+1, r, i, j));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, K;
    cin >> n >> K;
    vector<ll> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<ll> dp_prev(n+1, INF), dp_cur(n+1, INF);
    dp_prev[0] = 0;
    // base k=1: prefix max
    for (int i = 1; i <= n; i++) dp_prev[i] = max(dp_prev[i-1], a[i]);

    for (int k = 2; k <= K; k++) {
        Beats st(n+1);
        st.build(1, 0, n, dp_prev);

        int left = k;
        for (int i = k; i <= n; i++) {
            // enforce max(a[j+1..i]) using range_chmax
            st.range_chmax(1, 0, n, k-1, i-1, *max_element(a.begin()+left, a.begin()+i+1));
            dp_cur[i] = st.range_min(1, 0, n, k-1, i-1);
        }
        dp_prev.swap(dp_cur);
        fill(dp_cur.begin(), dp_cur.end(), INF);
    }

    cout << dp_prev[n] << '\n';
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47