Submission #396489

#	Time	Username	Problem	Language	Result	Execution time	Memory
396489		rama_pang	Bigger segments (IZhO19_segments)	C++17	100 / 100	232 ms	28796 KiB

segments

#include <bits/stdc++.h>
using namespace std;

class SegTree {
 public:
  int sz;
  vector<long long> coords;
  vector<pair<int, int>> tree;

  SegTree(int sz, vector<long long> coords) : sz(sz), coords(coords), tree(2 * sz, {-1e9, -1e9}) {}

  void Update(long long p, pair<int, int> x) {
    p = lower_bound(begin(coords), end(coords), p) - begin(coords);
    if (p == sz) return;
    for (p += sz; p > 0; p /= 2) tree[p] = max(tree[p], x);
  }

  pair<int, int> Query(long long l, long long r) {
    l = lower_bound(begin(coords), end(coords), l) - begin(coords);
    r = upper_bound(begin(coords), end(coords), r) - begin(coords);
    pair<int, int> res = {-1e9, -1e9};
    for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
      if (l & 1) res = max(res, tree[l++]);
      if (r & 1) res = max(res, tree[--r]);
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;

  vector<long long> A(N + 1);
  for (int i = 1; i <= N; i++) {
    cin >> A[i];
    A[i] += A[i - 1];
  }

  // dp[i] = (max_segments, last_segment_sum)
  // it is always optimal to maximize max_segments first, since
  // the more segments, the smaller the last_sum.
  //
  // dp[i] = j < i: (dp[j].seg + 1, prefix[i] - prefix[j]) if prefix[i] - prefix[j] >= dp[j].sum
  // criteria: prefix[i] >= dp[j].sum + prefix[j]
  // put (dp[j]) on position (dp[j].sum + prefix[j]), then:
  // We want max in position <= prefix[i]; find maximum possible j with maximum possible seg
  //   (since we want to minimize prefix[i] - prefix[j])
  // Just use segment tree. Time complexity: O(N log N).

  SegTree seg(N + 1, A);
  vector<pair<int, long long>> dp(N + 1);
  dp[0] = {0, 0};
  seg.Update(0, {0, 0});
  for (int i = 1; i <= N; i++) {
    auto q = seg.Query(0, A[i]);
    dp[i] = {q.first + 1, A[i] - A[q.second]};
    seg.Update(dp[i].second + A[i], {dp[i].first, i});
  }

  cout << dp[N].first << '\n';
  return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27