#949986 (C++23) No.2627 Unnatural Pitch

• 問題: No.2627 Unnatural Pitch
• ユーザー: Kude
• 提出日時: 2024-02-10 21:58:00
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 152 ms / 4,000 ms
• コード長: 5,059 bytes
• コンパイル時間: 4,325 ms
• コンパイル使用メモリ: 299,776 KB
• 実行使用メモリ: 23,296 KB
• 最終ジャッジ日時: 2024-02-10 21:58:08
• 合計ジャッジ時間: 7,825 ms
• ジャッジサーバーID （参考情報）: judge12 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,676 KB
testcase_01	AC	1 ms; 6,676 KB
testcase_02	AC	2 ms; 6,676 KB
testcase_03	AC	2 ms; 6,676 KB
testcase_04	AC	63 ms; 14,696 KB
testcase_05	AC	59 ms; 14,696 KB
testcase_06	AC	70 ms; 15,612 KB
testcase_07	AC	41 ms; 6,676 KB
testcase_08	AC	57 ms; 6,676 KB
testcase_09	AC	128 ms; 23,296 KB
testcase_10	AC	118 ms; 23,296 KB
testcase_11	AC	3 ms; 6,676 KB
testcase_12	AC	3 ms; 6,676 KB
testcase_13	AC	1 ms; 6,676 KB
testcase_14	AC	3 ms; 6,676 KB
testcase_15	AC	3 ms; 6,676 KB
testcase_16	AC	134 ms; 22,220 KB
testcase_17	AC	146 ms; 22,220 KB
testcase_18	AC	152 ms; 22,220 KB
testcase_19	AC	125 ms; 22,224 KB
testcase_20	AC	58 ms; 11,928 KB
testcase_21	AC	67 ms; 12,312 KB
testcase_22	AC	117 ms; 22,252 KB
testcase_23	AC	56 ms; 11,672 KB
testcase_24	AC	76 ms; 13,976 KB
testcase_25	AC	81 ms; 14,104 KB

ソースコード

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;


auto floor_div(signed_integral auto x, signed_integral auto y) {
  return x / y - ((x ^ y) < 0 && x % y != 0);
}
template <integral T>
T floor_div(T x, unsigned_integral auto y) {
  return x >= 0 ? T(x / y) : -T(-x / y + (-x % y != 0));
}
auto ceil_div(signed_integral auto x, signed_integral auto y) {
  return x / y + ((x ^ y) >= 0 && x % y != 0);
}
template <integral T>
T ceil_div(T x, unsigned_integral auto y) {
  return x >= 0 ? T(x / y + (x % y != 0)) : -T(-x / y);
}

template <class T, class Comp = less<T>>
struct erasable_priority_queue {
  priority_queue<T, vector<T>, Comp> q, q_erase;
  void push(T x) { q.push(move(x)); }
  template <class... Args>
  void emplace(Args&&... args) {
    q.emplace(forward<Args>(args)...);
  }
  void erase(T x) { q_erase.push(move(x)); }
  decltype(auto) top() {
    assert(!empty());
    expose_top();
    return q.top();
  }
  void pop() {
    assert(!empty());
    expose_top();
    q.pop();
  }
  int size() { return int(q.size()) - int(q_erase.size()); }
  bool empty() { return !size(); }
  void expose_top() {
    while (!q_erase.empty() && q_erase.top() == q.top()) {
      q_erase.pop();
      q.pop();
    }
  }
};

template <class T = long long, class PQMax = priority_queue<T>,
          class PQMin = priority_queue<T, vector<T>, greater<T>>>
struct SlopeTrick {
  static constexpr T INF = numeric_limits<T>::max() / 3;
  T min_f = 0;

  // acutual value of x in L is ADD_add_L(x) = x + add_L
  T add_L = 0, add_R = 0;
  PQMax L;
  PQMin R;

  T top_L() { return L.empty() ? -INF : L.top() + add_L; }
  T top_R() { return R.empty() ? +INF : R.top() + add_R; }
  void push_L(T x) { L.push(x - add_L); }
  void push_R(T x) { R.push(x - add_R); }
  T pushpop_L(T x) {
    T L_max = top_L();
    if (x >= L_max) return x;
    L.pop();
    push_L(x);
    return L_max;
  }
  T pushpop_R(T x) {
    T R_min = top_R();
    if (x <= R_min) return x;
    R.pop();
    push_R(x);
    return R_min;
  }

  // f(x) += c
  void add_constant(T c) { min_f += c; }
  // f(x) += max(x - a, 0)
  void add_right_slope(T a) {
    min_f += max<T>(top_L() - a, 0);
    push_R(pushpop_L(a));
  }
  // f(x) += max(a - x, 0)
  void add_left_slope(T a) {
    min_f += max<T>(a - top_R(), 0);
    push_L(pushpop_R(a));
  }
  // f(x) += abs(x - a)
  void add_v(T a) {
    add_right_slope(a);
    add_left_slope(a);
  }

  void shift(T a, T b) {
    assert(a <= b);
    add_L += a;
    add_R += b;
  }
  void shift(T a) { shift(a, a); }

  // f(x) -= max(x - a, 0)
  void erase_right_slope(T a) {
    if (top_R() <= a) {
      R.erase(a - add_R);
    } else {
      min_f -= top_R() - a;
      L.erase(a - add_L);
      push_L(top_R());
      R.pop();
    }
  }
  // f(x) -= max(a - x, 0)
  void erase_left_slope(T a) {
    if (a <= top_L()) {
      L.erase(a - add_L);
    } else {
      min_f -= a - top_L();
      R.erase(a - add_R);
      push_R(top_L());
      L.pop();
    }
  }
  // f(x) -= abs(x - a)
  void erase_v(T a) {
    erase_right_slope(a);
    erase_left_slope(a);
  }
};

template <class T>
using ErasableSlopeTrick = SlopeTrick < T,
      erasable_priority_queue<T>, erasable_priority_queue<T, greater<T>>>;

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  ll l, r;
  cin >> n >> k >> l >> r;
  r++;
  ErasableSlopeTrick<ll> st;
  vector<tuple<int, bool, ll>> shift_slope;
  rep(_, n) {
    ll a;
    cin >> a;
    ll la = l - a, ra = r - a;
    auto lc = ceil_div(la, k);
    auto rc = ceil_div(ra, k) - 1;
    st.add_left_slope(lc);
    st.add_right_slope(rc);
    int nxt_l = la % k;
    if (nxt_l < 0) nxt_l += k;
    int nxt_r = ra % k;
    if (nxt_r < 0) nxt_r += k;
    if (nxt_l) shift_slope.emplace_back(nxt_l, 0, lc);
    if (nxt_r) shift_slope.emplace_back(nxt_r, 1, rc);
  }
  ll ans = st.min_f;
  sort(all(shift_slope), [](const auto& x, const auto& y) { return get<0>(x) > get<0>(y); });
  rep(r, k) {
    if (shift_slope.empty()) break;
    r = get<0>(shift_slope.back());
    while (shift_slope.size() && get<0>(shift_slope.back()) == r) {
      auto [_, t, a] = shift_slope.back();
      shift_slope.pop_back();
      if (!t) st.erase_left_slope(a), st.add_left_slope(a - 1);
      else st.erase_right_slope(a), st.add_right_slope(a - 1);
    }
    chmin(ans, st.min_f);
  }
  assert(shift_slope.empty());
  cout << ans << '\n';
}