Advertisement
Guest User

Untitled

a guest
Feb 16th, 2020
349
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.63 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct RMQ {
  6.   const int kInf = numeric_limits<int>::min();
  7.     vector<vector<int>> rmq;
  8.  
  9.     RMQ(const vector<int>& V) {
  10.         int n = V.size(), on = 1, depth = 1;
  11.         while (on < n) on *= 2, ++depth;
  12.         rmq.assign(depth, V);
  13.     for (int i = 0; i < depth - 1; ++i)
  14.       for (int j = 0; j < n; ++j) {
  15.         rmq[i + 1][j] = max(rmq[i][j],
  16.           rmq[i][min(n - 1, j + (1 << i))]);
  17.       }
  18.     }
  19.  
  20.     int Query(int a, int b) const {
  21.     ++b;
  22.         if (b <= a) return kInf;
  23.         int dep = 31 - __builtin_clz(b - a); // log(b - a)
  24.         return max(rmq[dep][a], rmq[dep][b - (1 << dep)]);
  25.     }
  26. };
  27.  
  28. struct Sums {
  29.   int n;
  30.   vector<long long> s;
  31.  
  32.   Sums(const vector<int>& v) : n(v.size()), s(n) {
  33.     for (int i = 0; i < n; ++i) {
  34.       s[i] = v[i];
  35.       if (i > 0)
  36.         s[i] += s[i - 1];
  37.     }
  38.   }
  39.  
  40.   long long Query(int a, int b) const {
  41.     long long ans = s[b];
  42.     if (a > 0) ans -= s[a - 1];
  43.     return ans;
  44.   }
  45. };
  46.  
  47. vector<int> Solve(const RMQ& rmq, const Sums& sums,
  48.   const vector<int>& v, int k, int l, bool adapt) {
  49.   int n = v.size();
  50.  
  51.   vector<int> ans = {-1, l - 1};
  52.   for (int i = 1; i < k; ++i) {
  53.     for (int j = ans.back() + 1; j < n; ++j) {
  54.       long long s1 = sums.Query(
  55.           ans[ans.size() - 2] + 1,
  56.           ans[ans.size() - 1]);
  57.       int m1 = rmq.Query(
  58.           ans[ans.size() - 2] + 1,
  59.           ans[ans.size() - 1]);
  60.       long long s2 = sums.Query(ans[ans.size() - 1] + 1, j);
  61.       int m2 = rmq.Query(ans[ans.size() - 1] + 1, j);
  62.       if (abs(s1 - s2) <= max(m1, m2)) {
  63.         ans.push_back(j);
  64.         break;
  65.       }
  66.     }
  67.   }
  68.  
  69.   if (ans.size() <= k || !adapt) {
  70.     ans.erase(ans.begin());
  71.     return ans;
  72.   }
  73.  
  74.   assert(ans.size() == k + 1);
  75.  
  76.   ans.back() = n - 1;
  77.   int ch = 1;
  78.   int iters = 0;
  79.   while (ch--) {
  80.     ++iters;
  81.     for (int i = k - 1; i > 0; --i) {
  82.       if (ch) {
  83.         i += 2; ch = 0;
  84.         i = min(i, k - 1);
  85.       }
  86.       int state = 0;
  87.       int fst = 1;
  88.  
  89.       while (true) {
  90.         long long s1 = sums.Query(
  91.             ans[i - 1] + 1, ans[i]);
  92.         int m1 = rmq.Query(ans[i - 1] + 1, ans[i]);
  93.         long long s2 = sums.Query(
  94.             ans[i] + 1, ans[i + 1]);
  95.         int m2 = rmq.Query(ans[i] + 1, ans[i + 1]);
  96.  
  97.        
  98.         if (abs(s1 - s2) <= max(m1, m2)) {
  99.           if (fst) break;
  100.           state = 1;
  101.         } else if (state == 1) {
  102.           --ans[i];
  103.           break;
  104.         }
  105.         fst = 0;
  106.        
  107.         if (ans[i] + 1 == ans[i + 1]) {
  108.           if (state == 0) {
  109.             ans.push_back(-1);
  110.             return ans;
  111.           }
  112.           break;
  113.         }
  114.  
  115.         ++ans[i];
  116.         ch = 1;
  117.       }
  118.     }
  119.   }
  120. //   cerr << "ITERS: " << iters << endl;
  121.   ans.erase(ans.begin());
  122.   return ans;
  123. }
  124.  
  125. vector<int> Solve(vector<int> v, int k) {
  126.   int n = v.size();
  127.   RMQ rmq(v); Sums sums(v);
  128.   int pos = 0;
  129.  
  130.   int adv = 1;
  131.   for (int step = 1; step; adv ? step *= 2 : step /= 2) {
  132.     if (pos + step > n) {
  133.       adv = 0;
  134.     } else {
  135.       auto ans = Solve(rmq, sums, v, k, pos + step, false);
  136.       if (ans.size() < k) {
  137.         adv = 0;
  138.       } else {
  139.         pos += step;
  140.       }
  141.     }
  142.   }
  143.   assert(pos != -1);
  144.  
  145.   auto ans = Solve(rmq, sums, v, k, pos, true);
  146.   if (ans.size() == k) {
  147.     // ans.insert(ans.begin(), -1);
  148.     // // for (int i = 0; i <= k; ++i) {
  149.     // //   cerr << ans[i] + 1 << " ";
  150.     // // }
  151.     // // cerr << endl;
  152.     // for (int i = 1; i < k; ++i) {
  153.     //   long long s1 = sums.Query(
  154.     //       ans[i - 1] + 1, ans[i]);
  155.     //   int m1 = rmq.Query(ans[i - 1] + 1, ans[i]);
  156.     //   long long s2 = sums.Query(
  157.     //       ans[i] + 1, ans[i + 1]);
  158.     //   int m2 = rmq.Query(ans[i] + 1, ans[i + 1]);
  159.     //   if (abs(s1 - s2) > max(m1, m2)) {
  160.     //     assert(false);
  161.     //   }
  162.     // }
  163.     // ans.erase(ans.begin());
  164.     ans.pop_back();
  165.     return ans;
  166.   }
  167.  
  168.   assert(false);
  169. }
  170.  
  171. void Test() {
  172.   int N = 20, V = 20;
  173.   while (true) {
  174.     int n = rand() % N + 3;
  175.     vector<int> v(n);
  176.     for (int i = 0; i < n; ++i) {
  177.       v[i] = rand() % V + 1;
  178.     }
  179.     int k = rand() % (n - 2) + 3;
  180.    
  181.     cout << n << " " << k << endl;
  182.     for (int i = 0; i < n; ++i) {
  183.       cout << v[i] << " ";
  184.     }
  185.     cout << endl;
  186.    
  187.     Solve(v, k);
  188.   }
  189. }
  190.  
  191.  
  192. int main() {
  193.   ios_base::sync_with_stdio(false);
  194.   cin.tie(0);
  195.   // Test();
  196.   int n, k; cin >> n >> k;
  197.   vector<int> v(n);
  198.   for (int i = 0; i < n; ++i) {
  199.     cin >> v[i];
  200.   }
  201.   auto ans = Solve(v, k);
  202.   cout << "Yes\n";
  203.   for (int i = 0; i < k - 1; ++i)
  204.     cout << ans[i] + 1 << " ";
  205.   cout << '\n';
  206.  
  207.   return 0;
  208. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement