#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <map>
#include <set>
using namespace std;
vector<int64_t> p;
struct SegmentTree {
int64_t orig[262144];
int64_t vec[262144];
int64_t lazy[262144];
const int64_t INF = 1e18;
void push (int dum) {
if (lazy[dum] == -1) {
return;
}
lazy[2 * dum + 1] = lazy[dum];
lazy[2 * dum + 2] = lazy[dum];
vec[2 * dum + 1] = lazy[dum] + orig[2 * dum + 1];
vec[2 * dum + 2] = lazy[dum] + orig[2 * dum + 2];
lazy[dum] = -1;
}
void upd (int dum, int tl, int tr, int l, int r, int64_t x) {
if (tl >= l and tr <= r) {
lazy[dum] = x;
vec[dum] = orig[dum] + x;
return;
}
if (tl > r or l > tr) {
return;
}
push(dum);
upd(2 * dum + 1, tl, (tl + tr)/2, l, r, x);
upd(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r, x);
vec[dum] = min(vec[2 * dum + 1], vec[2 * dum + 2]);
}
int64_t query (int dum, int tl, int tr, int l, int r) {
if (tl >= l and tr <= r) {
return vec[dum];
}
if (tl > r or l > tr) {
return INF;
}
push(dum);
return min(query(2 * dum + 1, tl, (tl + tr)/2, l, r), query(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r));
}
void upd (int l, int r, int64_t x) {
upd(0, 0, (int)p.size() - 1, l, r, x);
}
int64_t query (int l, int r) {
return query(0, 0, (int)p.size() - 1, l, r);
}
void build (int dum, int tl, int tr) {
if (tl == tr) {
orig[dum] = p[tl];
return;
}
build(2 * dum + 1, tl, (tl + tr)/2);
build(2 * dum + 2, (tl + tr)/2 + 1, tr);
orig[dum] = min(orig[2 * dum + 1], orig[2 * dum + 2]);
}
void reset () {
for (int i = 0; i < 2 * p.size(); i++) {
orig[i] = 0, lazy[i] = -1;
}
build(0, 0, (int)p.size() - 1);
for (int i = 0; i < 2 * p.size(); i++) {
vec[i] = orig[i];
}
}
SegmentTree () {
int n = p.size();
for (int i = 0; i < 2 * n; i++) {
orig[i] = 0;
lazy[i] = -1;
}
build(0, 0, n - 1);
for (int i = 0; i < 2 * n; i++) {
vec[i] = orig[i];
}
}
};
struct SparseTable {
int64_t dp[131072][25];
int64_t query (int l, int r) {
int sz = log2(r - l + 1);
return min(dp[l][sz], dp[r - (1 << sz) + 1][sz]);
}
void upd (vector<int64_t> a) {
int n = a.size();
for (int j = 0; j < 25; j++) {
for (int i = 0; i < n; i++) {
if (j == 0) {
dp[i][j] = a[i];
} else {
dp[i][j] = min(dp[i][j - 1], dp[min(i + (1 << (j - 1)), (int)dp.size() - 1)][j - 1]);
}
}
}
}
};
int main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, K;
cin >> N >> K;
vector<int64_t> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int64_t INF = 1e17;
vector<int64_t> cur(N + 1);
p.assign(N + 1, INF), cur.assign(N + 1, INF);
for (int j = 1; j <= N; j++) {
p[j] = ((j == 1) ? arr[0] : max(p[j - 1], arr[j - 1]));
}
for (int i = 0; i < arr.size(); i++) {
arr[i] = -arr[i];
}
SparseTable st_a(N);
st_a.upd(arr);
for (int i = 0; i < arr.size(); i++) {
arr[i] = -arr[i];
}
while (__builtin_popcount(p.size()) != 1) {
p.push_back(0);
cur.push_back(0);
}
SparseTable st_p;
SegmentTree val;
for (int i = 2; i <= K; i++) {
val.reset();
st_p.upd(p);
for (int j = 1; j <= N; j++) {
if (j == 1) {
cur[j] = p[0] + arr[0];
} else {
cur[j] = INF;
int64_t myMax = 0;
int ind = -1;
int l = 0;
int r = j - 1;
while (l != r) {
int m = (l + r)/2;
if (st_a.query(m, j - 1) == -arr[j - 1]) {
r = m;
} else {
l = m + 1;
}
}
ind = l;
val.upd(ind, j - 1, arr[j - 1]);
cur[j] = min(val.query(0, ind - 1), arr[j - 1] + st_p.query(ind, j - 1));
}
}
swap(cur, p);
}
cout << p[N];
}
Compilation message
blocks.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("O3")
|
blocks.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
7 | #pragma GCC optimization ("unroll-loops")
|
blocks.cpp: In member function 'void SegmentTree::reset()':
blocks.cpp:67:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < 2 * p.size(); i++) {
| ~~^~~~~~~~~~~~~~
blocks.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for (int i = 0; i < 2 * p.size(); i++) {
| ~~^~~~~~~~~~~~~~
blocks.cpp: In member function 'void SparseTable::upd(std::vector<long int>)':
blocks.cpp:100:85: error: request for member 'size' in '((SparseTable*)this)->SparseTable::dp', which is of non-class type 'int64_t [131072][25]' {aka 'long int [131072][25]'}
100 | dp[i][j] = min(dp[i][j - 1], dp[min(i + (1 << (j - 1)), (int)dp.size() - 1)][j - 1]);
| ^~~~
blocks.cpp: In function 'int main()':
blocks.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for (int i = 0; i < arr.size(); i++) {
| ~~^~~~~~~~~~~~
blocks.cpp:124:23: error: no matching function for call to 'SparseTable::SparseTable(int&)'
124 | SparseTable st_a(N);
| ^
blocks.cpp:87:8: note: candidate: 'SparseTable::SparseTable()'
87 | struct SparseTable {
| ^~~~~~~~~~~
blocks.cpp:87:8: note: candidate expects 0 arguments, 1 provided
blocks.cpp:87:8: note: candidate: 'constexpr SparseTable::SparseTable(const SparseTable&)'
blocks.cpp:87:8: note: no known conversion for argument 1 from 'int' to 'const SparseTable&'
blocks.cpp:87:8: note: candidate: 'constexpr SparseTable::SparseTable(SparseTable&&)'
blocks.cpp:87:8: note: no known conversion for argument 1 from 'int' to 'SparseTable&&'
blocks.cpp:126:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for (int i = 0; i < arr.size(); i++) {
| ~~^~~~~~~~~~~~
blocks.cpp:143:25: warning: unused variable 'myMax' [-Wunused-variable]
143 | int64_t myMax = 0;
| ^~~~~
