oj.uz

Submission #870336

# Submission time Handle Problem Language Result Execution time Memory
870336 2023-11-07T13:05:32 Z truongdoan2012 K blocks (IZhO14_blocks) C++17
0 / 100
 76 ms 163668 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

using i64 = long long;

class segtree {
public:
  struct node {
    // don't forget to set default value (used for leaves)
    // not necessarily neutral element!
    i64 a = 0;
    int pos = 0;

    void apply(int l, int r, i64 v) {
      a = v;
      pos = l;
    }
  };

  node unite(const node &a, const node &b) const {
    node res = b;
    if (a.a < b.a)
      res = a;
    return res;
  }

  inline void push(int x, int l, int r) {
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    // push from x into (x + 1) and z
    /*
        if (tree[x].add != 0) {
          tree[x + 1].apply(l, y, tree[x].add);
          tree[z].apply(y + 1, r, tree[x].add);
          tree[x].add = 0;
        }
    */
  }

  inline void pull(int x, int z) { tree[x] = unite(tree[x + 1], tree[z]); }

  int n;
  vector<node> tree;

  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M> void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tree[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }

  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M &...v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }

  int find_first_knowingly(int x, int l, int r,
                           const function<bool(const node &)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int x, int l, int r, int ll, int rr,
                 const function<bool(const node &)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  int find_last_knowingly(int x, int l, int r,
                          const function<bool(const node &)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int x, int l, int r, int ll, int rr,
                const function<bool(const node &)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }

  template <typename M> segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }

  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M> void modify(int ll, int rr, const M &...v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once

  int find_first(int ll, int rr, const function<bool(const node &)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }

  int find_last(int ll, int rr, const function<bool(const node &)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};
const int N = 1e5 + 10;
i64 dp[N][101]; // min val khi chia i phan tu vao j nhom
i64 a[N], pm[N];

void solve() {
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pm[i] = max(pm[i - 1], a[i]);
  }
  memset(dp, 127, sizeof dp);
  for (int i = 1; i <= n; i++) {
    dp[i][1] = pm[i];
  }
  vector<int> l(n);
  {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
      while (!st.empty() && a[st.top()] <= a[i]) {
        st.pop();
      }
      if (st.empty())
        l[i] = 1;
      else
        l[i] = st.top();
    }
  }
  for (int j = 2; j <= k; j++) {
    segtree st(n + 10);
    for (int i = 1; i <= n; i++) {
      st.modify(i, i, dp[i][j - 1]);
    }
    for (int i = j; i <= n; i++) {
      auto p = st.get(1, i - 1);
      dp[i][j] = min(dp[i][j], st.get(l[i], i).a + a[i]);
    }
  }
  cout << dp[n][k];
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int TC = 1;
  // cin >> TC;
  while (TC--) {
    solve();
  }
}

Compilation message

blocks.cpp: In member function 'void segtree::push(int, int, int)':
blocks.cpp:36:9: warning: unused variable 'z' [-Wunused-variable]
   36 |     int z = x + ((y - l + 1) << 1);
      |         ^
blocks.cpp: In function 'void solve()':
blocks.cpp:269:12: warning: variable 'p' set but not used [-Wunused-but-set-variable]
  269 |       auto p = st.get(1, i - 1);
      |            ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 80724 KB Output is correct
2 Correct 12 ms 80732 KB Output is correct
3 Correct 10 ms 80864 KB Output is correct
4 Correct 10 ms 80732 KB Output is correct
5 Correct 10 ms 80728 KB Output is correct
6 Correct 10 ms 80728 KB Output is correct
7 Correct 10 ms 80920 KB Output is correct
8 Runtime error 72 ms 163552 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 80728 KB Output is correct
2 Correct 10 ms 80732 KB Output is correct
3 Correct 10 ms 80732 KB Output is correct
4 Correct 10 ms 80732 KB Output is correct
5 Correct 10 ms 80732 KB Output is correct
6 Correct 10 ms 80732 KB Output is correct
7 Correct 10 ms 80732 KB Output is correct
8 Runtime error 76 ms 163668 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 80724 KB Output is correct
2 Correct 12 ms 80732 KB Output is correct
3 Correct 10 ms 80864 KB Output is correct
4 Correct 10 ms 80732 KB Output is correct
5 Correct 10 ms 80728 KB Output is correct
6 Correct 10 ms 80728 KB Output is correct
7 Correct 10 ms 80920 KB Output is correct
8 Runtime error 72 ms 163552 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 80724 KB Output is correct
2 Correct 12 ms 80732 KB Output is correct
3 Correct 10 ms 80864 KB Output is correct
4 Correct 10 ms 80732 KB Output is correct
5 Correct 10 ms 80728 KB Output is correct
6 Correct 10 ms 80728 KB Output is correct
7 Correct 10 ms 80920 KB Output is correct
8 Runtime error 72 ms 163552 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -