Advertisement
HoBoCTb

Untitled

Aug 2nd, 2021
692
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.53 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define rep(i, a, b) for(auto (i) = a; (i) < (b); ++(i))
  5. #define all(x) begin(x), end(x)
  6. #define sz(x) (int)(x).size()
  7. typedef long long ll;
  8. typedef pair<int, int> pii;
  9. typedef pair<ll, ll> pll;
  10. typedef vector<int> vi;
  11. typedef vector<ll> vll;
  12.  
  13. #ifndef LOCAL
  14. #define cerr if(0) cerr
  15. #endif
  16.  
  17. int level(int x) {
  18.     return 31 - __builtin_clz(x);
  19. }
  20.  
  21. //#define int long long
  22.  
  23. struct node {
  24.     int l, r, p;
  25. };
  26.  
  27. constexpr int N = 2e5 + 5;
  28. pll f[N];
  29. int n;
  30. int t[2 * N];
  31.  
  32. vi v;
  33. vector<vi> jmp;
  34. void init(const vi& V) {
  35.     jmp.resize(1, V);
  36.     for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
  37.         jmp.emplace_back(sz(V) - pw * 2 + 1);
  38.         rep(j, 0, sz(jmp[k]))
  39.             jmp[k][j] = jmp[k - 1][j] | jmp[k - 1][j + pw];
  40.     }
  41. }
  42.  
  43. int query1(int a, int b) {
  44.     if (a == b) return 0;
  45.     int dep = 31 - __builtin_clz(b - a);
  46.     return jmp[dep][a] | jmp[dep][b - (1 << dep)];
  47. }
  48.  
  49. inline int combine(int a, int b) noexcept {
  50.     return a | b;
  51. }
  52.      
  53. inline void build() noexcept { for (int i = n - 1; i > 0; --i) t[i] = combine(t[i<<1], t[i<<1|1]); }
  54.      
  55. inline void modify(int p, int value) noexcept {
  56.     for (t[p += n] = value; p > 1; p >>= 1) t[p<<1] = combine(t[p], t[p^1]);
  57. }
  58.      
  59. inline int query(ll l, ll r) noexcept {
  60.     int res = 0;
  61.          
  62.     for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  63.         if (l&1) res = combine(res, t[l++]);
  64.         if (r&1) res = combine(t[--r], res);
  65.     }
  66.          
  67.     return res;
  68. }
  69.  
  70. ll lag;
  71.  
  72. inline pll calc(int i, int j) noexcept {
  73.     return {f[i].first + (ll)query1(i, j) + lag, f[i].second + 1ll};
  74. }
  75.  
  76. inline int find(node nd, int x) noexcept {
  77.     int l = nd.l - 1, r = nd.r;
  78.      
  79.     while (r - l > 1) {
  80.         int m = l + (r - l) / 2;
  81.          
  82.         if (calc(x, m).first <= calc(nd.p, m).first)
  83.             l = m;
  84.         else
  85.             r = m;
  86.     }
  87.      
  88.     return r;
  89. }
  90.  
  91. pll calcDP() {
  92.     fill(f, f + n + 5, pair{0, 0});
  93.     deque<node> q;
  94.     int sz = n + 1;
  95.     q.push_back({0, sz, 0});
  96.      
  97.     // [0, i) + [i, n)
  98.     rep(i, 1, sz) {
  99.         if (q.front().r == i) q.pop_front();
  100.          
  101.         q.front().l = i;
  102.          
  103.         f[i] = calc(q.front().p, i);
  104.         cerr << q.front().p << ' ';
  105.          
  106.         while (!q.empty() && calc(i, q.back().l).first > calc(q.back().p, q.back().l).first) {
  107.             q.pop_back();
  108.         }
  109.          
  110.         if (q.empty()) {
  111.             q.push_back({i, sz, i});
  112.         } else {
  113.             int pos = find(q.back(), i);
  114.             q.back().r = pos;
  115.             q.push_back({pos, sz, i});
  116.         }
  117.     }
  118.      
  119.     cerr << '\n';
  120.      
  121.     return f[n];
  122. }
  123.  
  124.  
  125. signed main() {
  126. #ifdef LOCAL
  127.     freopen("input.txt", "r", stdin);
  128. #endif
  129.     cin.tie(0)->sync_with_stdio(0);
  130.     cin.exceptions(cin.failbit);
  131.      
  132.     int k;
  133.     cin >> n >> k;
  134.     vi a(n);
  135.     rep(i, 0, n) {
  136.         cin >> a[i];
  137.         t[ i + n] = a[i];
  138.     }
  139.      
  140.     build();
  141.     a.push_back(0);
  142.     init(a);
  143.      
  144.     ll l = -3e12, r = 1;
  145.      
  146.     while (r - l > 1) {
  147.         ll m = l + (r - l) / 2;
  148.         lag = m;
  149.         pll res = calcDP();
  150.          
  151.         if (res.second > k) {
  152.             r = m;
  153.         } else {
  154.             l = m;
  155.         }
  156.     }
  157.     //
  158.     //    int l = -13;
  159.     lag = l;
  160.     pll res = calcDP();
  161.      
  162.     cerr << "\n";
  163.     for (int i = 0; i < n + 1; ++i) {
  164.         cerr << f[i].second << ' ';
  165.     }
  166.     cerr << "\n";
  167.      
  168.     cout << res.first - k * lag << '\n';
  169. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement