Submission #487905

#	Time	Username	Problem	Language	Result	Execution time	Memory
487905		SirCovidThe19th	K blocks (IZhO14_blocks)	C++17	53 / 100	1101 ms	66624 KiB

blocks

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2")

const int mx = 1e5 + 5;
 
int n, k, A[mx]; vector<int> stk;
 
struct Node{ int mnDP, vDP, vRange; };
 
template<int sz> struct ST{
    Node seg[262144]; int lz[262144];
 
    inline Node comb(Node a, Node b){ 
        if (a.vDP + a.vRange > b.vDP + b.vRange) swap(a, b);
        a.mnDP = min(a.mnDP, b.mnDP);
        return a;
    }
    inline Node comb1(int i, int j){
        Node a = seg[i], b = seg[j];
        if (lz[i]) a.vDP = a.mnDP, a.vRange = lz[i];
        if (lz[j]) b.vDP = b.mnDP, b.vRange = lz[j];
        return comb(a, b);
    }
    inline void push(int l, int r, int i){
        if (!lz[i]) return;
        seg[i].vRange = lz[i];
        if (l != r) lz[i * 2] = lz[i * 2 + 1] = lz[i];
        lz[i] = 0;
    }
    inline void upd(int x, int y, int vDP, int vR, int l = 0, int r = sz, int i = 1){
        push(l, r, i);
        if (l > y or r < x) return;
        if (l >= x and r <= y){ 
            if (vDP) seg[i].mnDP = seg[i].vDP = vDP; 
            if (vR) lz[i] = vR, push(l, r, i);
            if (l != r) seg[i] = comb1(i * 2, i * 2 + 1);
            return;
        }
        int mid = (l + r) / 2;
        upd(x, y, vDP, vR, l, mid, i * 2); upd(x, y, vDP, vR, mid + 1, r, i * 2 + 1);
        seg[i] = comb1(i * 2, i * 2 + 1);
    }
    inline Node query(int x, int y, int l = 0, int r = sz, int i = 1){
        push(l, r, i); 
        if (l > y or r < x) return {(int)1e9, (int)1e9, (int)1e9};
        if (l != r) seg[i] = comb1(i * 2, i * 2 + 1); 
        if (l >= x and r <= y) return seg[i];
        int mid = (l + r) / 2; 
        return comb(query(x, y, l, mid, i * 2), query(x, y, mid + 1, r, i * 2 + 1));
    }
};ST<mx> dp[101];
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k; 
    for (int j = 1; j <= k; j++) dp[j].upd(0, 0, 1e9, 0);
    for (int i = 1; i <= n; i++) dp[0].upd(i, i, 1e9, 0);
 
    for (int i = 1; i <= n; i++){
        cin >> A[i];
 
        while (!stk.empty() and A[stk.back()] < A[i]) stk.pop_back();
        int L = (stk.empty()) ? 0 : stk.back();
 
        for (int j = 1; j <= k; j++){
            dp[j - 1].upd(L, i - 1, 0, A[i]);
            Node ret = dp[j - 1].query(0, i - 1); 
            int ans = ret.vDP + ret.vRange;
            dp[j].upd(i, i, ans, 0);
 
            if (i == n and j == k) cout<<ans<<endl;
        }
        stk.push_back(i);
    }  
}

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