Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct RMQ {
- const int kInf = numeric_limits<int>::min();
- vector<vector<int>> rmq;
- RMQ(const vector<int>& V) {
- int n = V.size(), on = 1, depth = 1;
- while (on < n) on *= 2, ++depth;
- rmq.assign(depth, V);
- for (int i = 0; i < depth - 1; ++i)
- for (int j = 0; j < n; ++j) {
- rmq[i + 1][j] = max(rmq[i][j],
- rmq[i][min(n - 1, j + (1 << i))]);
- }
- }
- int Query(int a, int b) const {
- ++b;
- if (b <= a) return kInf;
- int dep = 31 - __builtin_clz(b - a); // log(b - a)
- return max(rmq[dep][a], rmq[dep][b - (1 << dep)]);
- }
- };
- struct Sums {
- int n;
- vector<long long> s;
- Sums(const vector<int>& v) : n(v.size()), s(n) {
- for (int i = 0; i < n; ++i) {
- s[i] = v[i];
- if (i > 0)
- s[i] += s[i - 1];
- }
- }
- long long Query(int a, int b) const {
- long long ans = s[b];
- if (a > 0) ans -= s[a - 1];
- return ans;
- }
- };
- vector<int> Solve(const RMQ& rmq, const Sums& sums,
- const vector<int>& v, int k, int l, bool adapt) {
- int n = v.size();
- vector<int> ans = {-1, l - 1};
- for (int i = 1; i < k; ++i) {
- for (int j = ans.back() + 1; j < n; ++j) {
- long long s1 = sums.Query(
- ans[ans.size() - 2] + 1,
- ans[ans.size() - 1]);
- int m1 = rmq.Query(
- ans[ans.size() - 2] + 1,
- ans[ans.size() - 1]);
- long long s2 = sums.Query(ans[ans.size() - 1] + 1, j);
- int m2 = rmq.Query(ans[ans.size() - 1] + 1, j);
- if (abs(s1 - s2) <= max(m1, m2)) {
- ans.push_back(j);
- break;
- }
- }
- }
- if (ans.size() <= k || !adapt) {
- ans.erase(ans.begin());
- return ans;
- }
- assert(ans.size() == k + 1);
- ans.back() = n - 1;
- int ch = 1;
- int iters = 0;
- while (ch--) {
- ++iters;
- for (int i = k - 1; i > 0; --i) {
- if (ch) {
- i += 2; ch = 0;
- i = min(i, k - 1);
- }
- int state = 0;
- int fst = 1;
- while (true) {
- long long s1 = sums.Query(
- ans[i - 1] + 1, ans[i]);
- int m1 = rmq.Query(ans[i - 1] + 1, ans[i]);
- long long s2 = sums.Query(
- ans[i] + 1, ans[i + 1]);
- int m2 = rmq.Query(ans[i] + 1, ans[i + 1]);
- if (abs(s1 - s2) <= max(m1, m2)) {
- if (fst) break;
- state = 1;
- } else if (state == 1) {
- --ans[i];
- break;
- }
- fst = 0;
- if (ans[i] + 1 == ans[i + 1]) {
- if (state == 0) {
- ans.push_back(-1);
- return ans;
- }
- break;
- }
- ++ans[i];
- ch = 1;
- }
- }
- }
- // cerr << "ITERS: " << iters << endl;
- ans.erase(ans.begin());
- return ans;
- }
- vector<int> Solve(vector<int> v, int k) {
- int n = v.size();
- RMQ rmq(v); Sums sums(v);
- int pos = 0;
- int adv = 1;
- for (int step = 1; step; adv ? step *= 2 : step /= 2) {
- if (pos + step > n) {
- adv = 0;
- } else {
- auto ans = Solve(rmq, sums, v, k, pos + step, false);
- if (ans.size() < k) {
- adv = 0;
- } else {
- pos += step;
- }
- }
- }
- assert(pos != -1);
- auto ans = Solve(rmq, sums, v, k, pos, true);
- if (ans.size() == k) {
- // ans.insert(ans.begin(), -1);
- // // for (int i = 0; i <= k; ++i) {
- // // cerr << ans[i] + 1 << " ";
- // // }
- // // cerr << endl;
- // for (int i = 1; i < k; ++i) {
- // long long s1 = sums.Query(
- // ans[i - 1] + 1, ans[i]);
- // int m1 = rmq.Query(ans[i - 1] + 1, ans[i]);
- // long long s2 = sums.Query(
- // ans[i] + 1, ans[i + 1]);
- // int m2 = rmq.Query(ans[i] + 1, ans[i + 1]);
- // if (abs(s1 - s2) > max(m1, m2)) {
- // assert(false);
- // }
- // }
- // ans.erase(ans.begin());
- ans.pop_back();
- return ans;
- }
- assert(false);
- }
- void Test() {
- int N = 20, V = 20;
- while (true) {
- int n = rand() % N + 3;
- vector<int> v(n);
- for (int i = 0; i < n; ++i) {
- v[i] = rand() % V + 1;
- }
- int k = rand() % (n - 2) + 3;
- cout << n << " " << k << endl;
- for (int i = 0; i < n; ++i) {
- cout << v[i] << " ";
- }
- cout << endl;
- Solve(v, k);
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- // Test();
- int n, k; cin >> n >> k;
- vector<int> v(n);
- for (int i = 0; i < n; ++i) {
- cin >> v[i];
- }
- auto ans = Solve(v, k);
- cout << "Yes\n";
- for (int i = 0; i < k - 1; ++i)
- cout << ans[i] + 1 << " ";
- cout << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement