Submission #1208103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208103		gatapdev	K blocks (IZhO14_blocks)	C++20	Compilation error	0 ms	0 KiB

blocks

const long long INF = LLONG_MAX/4;

// segment tree hỗ trợ range‐add & range‐min
struct SegTree {
    int n;
    vector<long long> st, lazy;
    SegTree(int _n): n(_n), st(4*n, INF), lazy(4*n, 0) {}
    
    void apply(int p, int l, int r, long long v) {
        st[p] += v;
        lazy[p] += v;
    }
    void push(int p, int l, int r) {
        if (lazy[p]!=0) {
            int m=(l+r)/2;
            apply(p<<1, l, m, lazy[p]);
            apply(p<<1|1, m+1, r, lazy[p]);
            lazy[p]=0;
        }
    }
    void pull(int p) {
        st[p] = min(st[p<<1], st[p<<1|1]);
    }
    
    void build(int p, int l, int r, vector<long long>& base) {
        if (l==r) {
            st[p] = base[l];
            return;
        }
        int m=(l+r)/2;
        build(p<<1, l, m, base);
        build(p<<1|1, m+1, r, base);
        pull(p);
    }
    void range_add(int p, int l, int r, int i, int j, long long v) {
        if (i>r||j<l) return;
        if (i<=l&&r<=j) {
            apply(p,l,r,v);
            return;
        }
        push(p,l,r);
        int m=(l+r)/2;
        range_add(p<<1, l, m, i, j, v);
        range_add(p<<1|1, m+1, r, i, j, v);
        pull(p);
    }
    long long 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];
        push(p,l,r);
        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)
        );
    }
};

// Trong phần main hoặc hàm tính DP cho từng k:
vector<long long> dp_prev(n+1), dp_cur(n+1);
dp_prev[0] = 0;
for(int i=1;i<=n;i++) dp_prev[i]=INF;

for(int k=1;k<=K;k++){
    // 1) khởi base = dp_prev
    SegTree st(n+1);
    st.build(1, 0, n, dp_prev);
    
    // 2) monotonic stack để track các interval
    vector<int> stk;
    // Mảng để lưu biên trái của mỗi phần tử trong stack
    vector<int> left(n+1);
    
    stk.reserve(n);
    for(int i=1;i<=n;i++){
        int L = i;
        // pop các a[stk.top] <= a[i]
        while(!stk.empty() && a[stk.back()] <= a[i]){
            int t = stk.back(); stk.pop_back();
            int lt = left[t];
            // với mọi j trong [lt-1, t-1], max cũ = a[t] -> cập nhật thành a[i]
            st.range_add(1, 0, n, lt-1, t-1, a[i] - a[t]);
            L = lt;
        }
        stk.push_back(i);
        left[i] = L;
        
        // bây giờ query dp_cur[i]
        dp_cur[i] = st.range_min(1, 0, n, 0, i-1);
    }
    // đổi mảng
    dp_prev = dp_cur;
    fill(dp_cur.begin(), dp_cur.end(), INF);
}

// Kết quả: dp_prev[n]
cout << dp_prev[n] << "\n";

Compilation message (stderr)

blocks.cpp:1:23: error: 'LLONG_MAX' was not declared in this scope
    1 | const long long INF = LLONG_MAX/4;
      |                       ^~~~~~~~~
blocks.cpp:1:1: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
  +++ |+#include <climits>
    1 | const long long INF = LLONG_MAX/4;
blocks.cpp:6:5: error: 'vector' does not name a type
    6 |     vector<long long> st, lazy;
      |     ^~~~~~
blocks.cpp:25:37: error: 'vector' has not been declared
   25 |     void build(int p, int l, int r, vector<long long>& base) {
      |                                     ^~~~~~
blocks.cpp:25:43: error: expected ',' or '...' before '<' token
   25 |     void build(int p, int l, int r, vector<long long>& base) {
      |                                           ^
blocks.cpp: In constructor 'SegTree::SegTree(int)':
blocks.cpp:7:29: error: class 'SegTree' does not have any field named 'st'
    7 |     SegTree(int _n): n(_n), st(4*n, INF), lazy(4*n, 0) {}
      |                             ^~
blocks.cpp:7:43: error: class 'SegTree' does not have any field named 'lazy'
    7 |     SegTree(int _n): n(_n), st(4*n, INF), lazy(4*n, 0) {}
      |                                           ^~~~
blocks.cpp: In member function 'void SegTree::apply(int, int, int, long long int)':
blocks.cpp:10:9: error: 'st' was not declared in this scope; did you mean 'std'?
   10 |         st[p] += v;
      |         ^~
      |         std
blocks.cpp:11:9: error: 'lazy' was not declared in this scope
   11 |         lazy[p] += v;
      |         ^~~~
blocks.cpp: In member function 'void SegTree::push(int, int, int)':
blocks.cpp:14:13: error: 'lazy' was not declared in this scope
   14 |         if (lazy[p]!=0) {
      |             ^~~~
blocks.cpp: In member function 'void SegTree::pull(int)':
blocks.cpp:22:9: error: 'st' was not declared in this scope; did you mean 'std'?
   22 |         st[p] = min(st[p<<1], st[p<<1|1]);
      |         ^~
      |         std
blocks.cpp:22:17: error: 'min' was not declared in this scope
   22 |         st[p] = min(st[p<<1], st[p<<1|1]);
      |                 ^~~
blocks.cpp: In member function 'void SegTree::build(int, int, int, int)':
blocks.cpp:27:13: error: 'st' was not declared in this scope; did you mean 'std'?
   27 |             st[p] = base[l];
      |             ^~
      |             std
blocks.cpp:27:21: error: 'base' was not declared in this scope
   27 |             st[p] = base[l];
      |                     ^~~~
blocks.cpp:31:27: error: 'base' was not declared in this scope
   31 |         build(p<<1, l, m, base);
      |                           ^~~~
blocks.cpp: In member function 'long long int SegTree::range_min(int, int, int, int, int)':
blocks.cpp:49:32: error: 'st' was not declared in this scope; did you mean 'std'?
   49 |         if (i<=l&&r<=j) return st[p];
      |                                ^~
      |                                std
blocks.cpp:52:16: error: 'min' was not declared in this scope
   52 |         return min(
      |                ^~~
blocks.cpp: At global scope:
blocks.cpp:60:1: error: 'vector' does not name a type
   60 | vector<long long> dp_prev(n+1), dp_cur(n+1);
      | ^~~~~~
blocks.cpp:61:1: error: 'dp_prev' does not name a type
   61 | dp_prev[0] = 0;
      | ^~~~~~~
blocks.cpp:62:1: error: expected unqualified-id before 'for'
   62 | for(int i=1;i<=n;i++) dp_prev[i]=INF;
      | ^~~
blocks.cpp:62:13: error: 'i' does not name a type
   62 | for(int i=1;i<=n;i++) dp_prev[i]=INF;
      |             ^
blocks.cpp:62:18: error: 'i' does not name a type
   62 | for(int i=1;i<=n;i++) dp_prev[i]=INF;
      |                  ^
blocks.cpp:64:1: error: expected unqualified-id before 'for'
   64 | for(int k=1;k<=K;k++){
      | ^~~
blocks.cpp:64:13: error: 'k' does not name a type
   64 | for(int k=1;k<=K;k++){
      |             ^
blocks.cpp:64:18: error: 'k' does not name a type
   64 | for(int k=1;k<=K;k++){
      |                  ^
blocks.cpp:97:1: error: 'cout' does not name a type
   97 | cout << dp_prev[n] << "\n";
      | ^~~~