Submission #1217310

#TimeUsernameProblemLanguageResultExecution timeMemory
1217310lmaobruhK blocks (IZhO14_blocks)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; static const ll INF = (1LL<<60); static const int MAXN = 100000; // --- segment tree range-add + global-min --- struct Seg { struct Node { ll mn, lz; } st[4*MAXN]; // build không cần, vì ta khởi lại bằng memset inline void apply(int p, ll v) { st[p].mn += v; st[p].lz += v; } inline void push(int p) { if (st[p].lz) { apply(p<<1, st[p].lz); apply(p<<1|1, st[p].lz); st[p].lz = 0; } } inline void pull(int p) { st[p].mn = min(st[p<<1].mn, st[p<<1|1].mn); } // update range [i..j] += v void updR(int p, int l, int r, int i, int j, ll v) { if (i>r || j<l) return; if (i<=l && r<=j) { apply(p, v); return; } push(p); int m = (l+r)>>1; if (i <= m) updR(p<<1, l, m, i, j, v); if (j > m) updR(p<<1|1, m+1, r, i, j, v); pull(p); } // point set pos=idx to value (overwrite) void updP(int p, int l, int r, int idx, ll val) { if (l==r) { st[p].mn = val; st[p].lz = 0; return; } push(p); int m = (l+r)>>1; if (idx <= m) updP(p<<1, l, m, idx, val); else updP(p<<1|1, m+1, r, idx, val); pull(p); } inline ll query() const { return st[1].mn; } } seg; // --- globals --- int N, K; int A[MAXN+1]; ll dp_prev[MAXN+1], dp_cur[MAXN+1]; // stack: values và left‑indices int stk_val[MAXN+1], stk_lft[MAXN+1], stk_sz; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> K; for(int i = 1; i <= N; ++i) cin >> A[i]; // init dp_prev for(int i = 0; i <= N; ++i) dp_prev[i] = (i==0 ? 0 : INF); while(K--){ // reset segtree nodes [1..4N] memset(seg.st, 0x7f, sizeof seg.st); // xây lại mn = INF, lz = 0 for(int p = 1; p < 4*(N+1); ++p){ seg.st[p].mn = INF; seg.st[p].lz = 0; } stk_sz = 0; // i = 1 khởi tạo seg.updP(1, 0, N-1, 0, dp_prev[0]); stk_val[0] = A[1]; stk_lft[0] = 0; stk_sz = 1; seg.updR(1, 0, N-1, 0, 0, A[1]); for(int i = 1; i <= N; ++i){ if (i > 1){ // 1) set dp_prev[i-1] seg.updP(1, 0, N-1, i-1, dp_prev[i-1]); // 2) xử lý A[i] với monotonic stack int L = i - 1; while(stk_sz > 0 && stk_val[stk_sz-1] <= A[i]){ int v = stk_val[stk_sz-1]; int lf = stk_lft[stk_sz-1]; --stk_sz; seg.updR(1, 0, N-1, lf, L-1, -v); L = lf; } // push segment mới stk_val[stk_sz] = A[i]; stk_lft[stk_sz] = L; ++stk_sz; seg.updR(1, 0, N-1, L, i-1, A[i]); } dp_cur[i] = seg.query(); } // swap dp_prev / dp_cur memcpy(dp_prev, dp_cur, (N+1)*sizeof ll); } cout << dp_prev[N]; return 0; }

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:116:48: error: expected primary-expression before ')' token
  116 |         memcpy(dp_prev, dp_cur, (N+1)*sizeof ll);
      |                                                ^