Submission #1253746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253746		elkernos	Ants and Sugar (JOI22_sugar)	C++20	100 / 100	898 ms	109876 KiB

sugar

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

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...) (void)0
#endif

namespace R = ranges;
namespace V = views;
auto ra(auto x, auto y) { return R::iota_view(x, y); }
auto rae(auto x, auto y) { return ra(x, y + 1); }
using i64 = int64_t;

template <class T> class Compressor {
private:
  bool init_called = false;
  vector<T> v = {};

public:
  void add(int x) {
    assert(!init_called);
    v.emplace_back(x);
  }
  void init() {
    assert(!init_called);
    debug(v);
    init_called = true;
    R::sort(v);
    auto [l, r] = R::unique(v);
    v.erase(l, r);
    debug(v);
  }
  int operator[](int x) {
    assert(init_called);
    return R::lower_bound(v, x) - begin(v);
  }
  size_t size() { return std::size(v); }
};

class segtree_t {
private:
  int l, r, m;
  i64 lazy_add, lazy_split_add, split;
  segtree_t *left, *right;
  array<array<i64, 2>, 2> dp;

  void pull() {
    for (auto i : ra(0, 2)) {
      for (auto j : ra(0, 2)) {
        dp[i][j] = numeric_limits<i64>::min();
        for (auto k : ra(0, 2)) {
          dp[i][j] =
              max(dp[i][j], left->dp[i][k] + right->dp[k][j] - k * split);
        }
      }
    }
    for (auto i : ra(0, 2)) {
      dp[i][0] = max(dp[i][0], left->dp[i][0]);
      dp[0][i] = max(dp[0][i], right->dp[0][i]);
    }
  }
  void push() {
    for (auto rep : ra(0, 2)) {
      left->lazy_add += lazy_add;
      left->lazy_split_add += lazy_split_add;
      left->split += lazy_split_add;
      for (auto i : ra(0, 2)) {
        for (auto j : ra(0, 2)) {
          left->dp[i][j] += lazy_add;
        }
      }
      swap(left, right);
    }

    lazy_add = lazy_split_add = 0;
  }

public:
  i64 hall() { return dp[0][0]; }
  segtree_t(int l, int r)
      : l(l), r(r), m(midpoint(l, r)), lazy_add(0), lazy_split_add(0),
        split(0) {
    for (auto i : ra(0, 2)) {
      for (auto j : ra(0, 2)) {
        dp[i][j] = 0;
      }
    }
    if (l == r) {
      left = right = nullptr;
      return;
    }
    left = new segtree_t(l, m);
    right = new segtree_t(m + 1, r);
  }
  void add(int a, int b, int how_much) {
    if (l > b || r < a) {
      return;
    }
    if (a <= l && r <= b) {
      for (auto i : ra(0, 2)) {
        for (auto j : ra(0, 2)) {
          dp[i][j] += how_much;
        }
      }
      lazy_add += how_much;
      lazy_split_add += how_much;
      split += how_much;
      return;
    }

    push();

    if (a <= m && m < b) {
      split += how_much;
    }
    left->add(a, b, how_much);
    right->add(a, b, how_much);
    pull();
  }
};

void solve() {
  int q, l;
  cin >> q >> l;
  vector<tuple<int, int, int>> qs(q);

  Compressor<int> comp;
  for (auto &[t, x, a] : qs) {
    cin >> t >> x >> a;
    comp.add(x);
  }
  comp.init();

  i64 all = 0;
  segtree_t *seg = new segtree_t(0, comp.size());

  for (auto [t, x, add] : qs) {
    if (t == 1) {
      all += add;
      auto p = comp[x];
      seg->add(p, p, add);
    } else {
      auto a = comp[x - l];
      auto b = comp[x + l + 1] - 1;
      seg->add(a, b, -add);
    }

    cout << all - seg->hall() << '\n';
  }
}

int32_t main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t = 1;
  // cin >> t;
  for (auto tc_n : ra(0, t)) {
    debug(tc_n);
    solve();
    cout.flush();
  }
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 26 / 26
• Subtask 4: 52 / 52