Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define rep(i, a, b) for(auto (i) = a; (i) < (b); ++(i))
- #define all(x) begin(x), end(x)
- #define sz(x) (int)(x).size()
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef pair<ll, ll> pll;
- typedef vector<int> vi;
- typedef vector<ll> vll;
- #ifndef LOCAL
- #define cerr if(0) cerr
- #endif
- int level(int x) {
- return 31 - __builtin_clz(x);
- }
- //#define int long long
- struct node {
- int l, r, p;
- };
- constexpr int N = 2e5 + 5;
- pll f[N];
- int n;
- int t[2 * N];
- vi v;
- vector<vi> jmp;
- void init(const vi& V) {
- jmp.resize(1, V);
- for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
- jmp.emplace_back(sz(V) - pw * 2 + 1);
- rep(j, 0, sz(jmp[k]))
- jmp[k][j] = jmp[k - 1][j] | jmp[k - 1][j + pw];
- }
- }
- int query1(int a, int b) {
- if (a == b) return 0;
- int dep = 31 - __builtin_clz(b - a);
- return jmp[dep][a] | jmp[dep][b - (1 << dep)];
- }
- inline int combine(int a, int b) noexcept {
- return a | b;
- }
- inline void build() noexcept { for (int i = n - 1; i > 0; --i) t[i] = combine(t[i<<1], t[i<<1|1]); }
- inline void modify(int p, int value) noexcept {
- for (t[p += n] = value; p > 1; p >>= 1) t[p<<1] = combine(t[p], t[p^1]);
- }
- inline int query(ll l, ll r) noexcept {
- int res = 0;
- for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
- if (l&1) res = combine(res, t[l++]);
- if (r&1) res = combine(t[--r], res);
- }
- return res;
- }
- ll lag;
- inline pll calc(int i, int j) noexcept {
- return {f[i].first + (ll)query1(i, j) + lag, f[i].second + 1ll};
- }
- inline int find(node nd, int x) noexcept {
- int l = nd.l - 1, r = nd.r;
- while (r - l > 1) {
- int m = l + (r - l) / 2;
- if (calc(x, m).first <= calc(nd.p, m).first)
- l = m;
- else
- r = m;
- }
- return r;
- }
- pll calcDP() {
- fill(f, f + n + 5, pair{0, 0});
- deque<node> q;
- int sz = n + 1;
- q.push_back({0, sz, 0});
- // [0, i) + [i, n)
- rep(i, 1, sz) {
- if (q.front().r == i) q.pop_front();
- q.front().l = i;
- f[i] = calc(q.front().p, i);
- cerr << q.front().p << ' ';
- while (!q.empty() && calc(i, q.back().l).first > calc(q.back().p, q.back().l).first) {
- q.pop_back();
- }
- if (q.empty()) {
- q.push_back({i, sz, i});
- } else {
- int pos = find(q.back(), i);
- q.back().r = pos;
- q.push_back({pos, sz, i});
- }
- }
- cerr << '\n';
- return f[n];
- }
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- #endif
- cin.tie(0)->sync_with_stdio(0);
- cin.exceptions(cin.failbit);
- int k;
- cin >> n >> k;
- vi a(n);
- rep(i, 0, n) {
- cin >> a[i];
- t[ i + n] = a[i];
- }
- build();
- a.push_back(0);
- init(a);
- ll l = -3e12, r = 1;
- while (r - l > 1) {
- ll m = l + (r - l) / 2;
- lag = m;
- pll res = calcDP();
- if (res.second > k) {
- r = m;
- } else {
- l = m;
- }
- }
- //
- // int l = -13;
- lag = l;
- pll res = calcDP();
- cerr << "\n";
- for (int i = 0; i < n + 1; ++i) {
- cerr << f[i].second << ' ';
- }
- cerr << "\n";
- cout << res.first - k * lag << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement