Submission #1313351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313351		dm623	Feast (NOI19_feast)	C++20	100 / 100	365 ms	110744 KiB

feast

#include <algorithm>
#include <climits>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>

template <class segment_tree_template>
struct lazy_segment_tree : public segment_tree_template {
  using T = typename segment_tree_template::node_type;
  using L = typename segment_tree_template::lazy_type;
  using segment_tree_template::node_default_value;
  using segment_tree_template::lazy_default_value;
  using segment_tree_template::merge;
  using segment_tree_template::apply;

  int n = 0;
  std::vector<T> tree;
  std::vector<L> lazy;

  void pushdown(int t, int tl, int tr) {
    if (lazy[t] == lazy_default_value) return;
    int tm = (tl + tr) / 2;
    apply(tree[t * 2], lazy[t * 2], lazy[t], tl, tm);
    apply(tree[t * 2 + 1], lazy[t * 2 + 1], lazy[t], tm + 1, tr);
    lazy[t] = lazy_default_value;
  }

  void modify_point(int i, long long x, int t, int tl, int tr) {
    if (tl == tr) {
      tree[t] = T(tl, x);
      return;
    }
    pushdown(t, tl, tr);
    int tm = (tl + tr) / 2;
    if (i <= tm)
      modify_point(i, x, t * 2, tl, tm);
    else
      modify_point(i, x, t * 2 + 1, tm + 1, tr);
    tree[t] = merge(tree[t * 2], tree[t * 2 + 1]);
  }

  void update_range(int l, int r, L v, int t, int tl, int tr) {
    if (r < tl || tr < l) return;
    if (l <= tl && tr <= r) {
      apply(tree[t], lazy[t], v, tl, tr);
      return;
    }
    pushdown(t, tl, tr);
    int tm = (tl + tr) / 2;
    update_range(l, r, v, t * 2, tl, tm);
    update_range(l, r, v, t * 2 + 1, tm + 1, tr);
    tree[t] = merge(tree[t * 2], tree[t * 2 + 1]);
  }

  T query_range(int l, int r, int t, int tl, int tr) {
    if (r < tl || tr < l) return node_default_value;
    if (l <= tl && tr <= r) return tree[t];
    pushdown(t, tl, tr);
    int tm = (tl + tr) / 2;
    return merge(query_range(l, r, t * 2, tl, tm),
                 query_range(l, r, t * 2 + 1, tm + 1, tr));
  }

 public:
  lazy_segment_tree() = default;
  explicit lazy_segment_tree(int _n) { init(_n); }

  void init(int _n) {
    n = _n;
    tree.assign(4 * n, node_default_value);
    lazy.assign(4 * n, lazy_default_value);
  }

  void modify(int i, long long x) { modify_point(i, x, 1, 0, n - 1); }
  void update(int l, int r, L v) { update_range(l, r, v, 1, 0, n - 1); }
  T query(int l, int r) { return query_range(l, r, 1, 0, n - 1); }
};

struct range_max_subsequence_sum_range_negate_segment_tree_template {
  struct node_type {
    long long Mans = 0, Mpre = 0, Msuf = 0;
    int Lans = -1, Rans = -1, Bpre = -1, Bsuf = -1;

    long long mans = 0, mpre = 0, msuf = 0;
    int lans = INT_MAX, rans = INT_MAX, bpre = INT_MAX, bsuf = INT_MAX;

    long long sum = 0;

    node_type() = default;

    node_type(int i, long long x) {
      if (x > 0) {
        Mans = Mpre = Msuf = x;
        Lans = Rans = Bpre = Bsuf = i;

        mans = mpre = msuf = 0;
        lans = rans = bpre = i - 1;
        bsuf = i + 1;
      } else {
        Mans = Mpre = Msuf = 0;
        Lans = Rans = Bpre = i - 1;
        Bsuf = i + 1;

        mans = mpre = msuf = x;
        lans = rans = bpre = bsuf = i;
      }
      sum = x;
    }

    friend std::ostream& operator<<(std::ostream& os, const node_type& n) {
      return os << '{' << n.Mans << ", " << n.Mpre << ", " << n.Msuf << ", "
                << n.Lans << ", " << n.Rans << ", " << n.Bpre << ", " << n.Bsuf
                << ", " << n.mans << ", " << n.mpre << ", " << n.msuf << ", "
                << n.lans << ", " << n.rans << ", " << n.bpre << ", " << n.bsuf
                << ", " << n.sum << '}';
    }
  };

  using lazy_type = int;

  const node_type node_default_value = node_type();
  const lazy_type lazy_default_value = 0;

  node_type merge(const node_type& a, const node_type& b) {
    using namespace std;

    node_type ret;

    tie(ret.Mans, ret.Lans, ret.Rans) = max(
        {make_tuple(a.Mans, a.Lans, a.Rans),
         make_tuple(b.Mans, b.Lans, b.Rans),
         make_tuple(a.Msuf + b.Mpre, a.Bsuf, b.Bpre)});

    tie(ret.Mpre, ret.Bpre) =
        max(make_pair(a.Mpre, a.Bpre), make_pair(a.sum + b.Mpre, b.Bpre));

    tie(ret.Msuf, ret.Bsuf) =
        max(make_pair(a.Msuf + b.sum, a.Bsuf), make_pair(b.Msuf, b.Bsuf));

    tie(ret.mans, ret.lans, ret.rans) = min(
        {make_tuple(a.mans, a.lans, a.rans),
         make_tuple(b.mans, b.lans, b.rans),
         make_tuple(a.msuf + b.mpre, a.bsuf, b.bpre)});

    tie(ret.mpre, ret.bpre) =
        min(make_pair(a.mpre, a.bpre), make_pair(a.sum + b.mpre, b.bpre));

    tie(ret.msuf, ret.bsuf) =
        min(make_pair(a.msuf + b.sum, a.bsuf), make_pair(b.msuf, b.bsuf));

    ret.sum = a.sum + b.sum;
    return ret;
  }

  void apply(node_type& a, lazy_type& b, lazy_type, int, int) {
    node_type r;
    r.Mans = -a.mans;
    r.Mpre = -a.mpre;
    r.Msuf = -a.msuf;
    r.Lans = a.lans;
    r.Rans = a.rans;
    r.Bpre = a.bpre;
    r.Bsuf = a.bsuf;

    r.mans = -a.Mans;
    r.mpre = -a.Mpre;
    r.msuf = -a.Msuf;
    r.lans = a.Lans;
    r.rans = a.Rans;
    r.bpre = a.Bpre;
    r.bsuf = a.Bsuf;

    r.sum = -a.sum;

    a = r;
    b ^= 1;
  }
};

using range_max_subsequence_sum_range_negate_segment_tree =
    lazy_segment_tree<range_max_subsequence_sum_range_negate_segment_tree_template>;

int main() {
  int n, k;
  std::cin >> n >> k;

  std::vector<long long> a(n);
  for (auto& x : a) std::cin >> x;

  range_max_subsequence_sum_range_negate_segment_tree t(n);
  for (int i = 0; i < n; i++) t.modify(i, a[i]);

  long long r = 0;
  for (int i = 0; i < k; i++) {
    auto q = t.query(0, n - 1);
    if (q.Mans <= 0) break;
    r += q.Mans;
    t.update(q.Lans, q.Rans, 1);
  }

  std::cout << r << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29