結果

問題 No.2627 Unnatural Pitch
コンテスト
ユーザー Kude
提出日時 2024-02-09 23:49:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,721 bytes
コンパイル時間 4,281 ms
コンパイル使用メモリ 309,900 KB
実行使用メモリ 43,524 KB
最終ジャッジ日時 2024-09-28 16:42:04
合計ジャッジ時間 9,433 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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);
}

constexpr long long INF = 1002003004005006007;

template <class S>
struct value_compression : vector<S> {
  bool built = false;
  using VS = vector<S>;
  using VS::VS;
  value_compression(vector<S> v) : vector<S>(move(v)) {}
  void build() {
    sort(this->begin(), this->end());
    this->erase(unique(this->begin(), this->end()), this->end());
    built = true;
  }
  template <class T>
  void convert(T first, T last) {
    assert(built);
    for (; first != last; ++first) *first = (*this)(*first);
  }
  int operator()(S x) {
    assert(built);
    return lower_bound(this->begin(), this->end(), x) - this->begin();
  }
  void clear() {
    this->clear();
    built = false;
  }
};

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  ll l, r;
  cin >> n >> k >> l >> r;
  r++;
  VL addl, addr;
  vector<tuple<int, int, ll, ll>> add_seg;
  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;
    addl.emplace_back(lc);
    addr.emplace_back(rc);
    int nxt_l = (la - 1) % k;
    if (nxt_l < 0) nxt_l += k;
    int nxt_r = (ra - 1) % k;
    if (nxt_r < 0) nxt_r += k;
    if (nxt_l) add_seg.emplace_back(nxt_l, -1, -INF, lc);
    if (nxt_r) add_seg.emplace_back(nxt_r, 1, rc, INF);
  }
  value_compression<ll> vc;
  for (ll x : addl) vc.emplace_back(x);
  for (ll x : addr) vc.emplace_back(x);
  for (auto [t, v, l, r] : add_seg) vc.emplace_back(l), vc.emplace_back(r);
  vc.build();
  int sz = vc.size();
  VL init(sz);
  {
    ll a = 0, b = 0;
    sort(rall(addl));
    sort(rall(addr));
    for (ll x : addl) a--, b += x;
    rep(i, sz) {
      ll x = vc[i];
      while (addl.size() && addl.back() == x) {
        a++, b -= x;
        addl.pop_back();
      }
      while (addr.size() && addr.back() == x) {
        a++, b -= x;
        addr.pop_back();
      }
      ll v;
      if (__builtin_mul_overflow(x, a, &v)) v = INF;
      else v += b;
      init[i] = v;
    }
  }
  lazy_segtree<ll, [](ll x, ll y) { return min(x, y); }, []() { return INF; }, int, [](int f, ll x) { return x >= INF ? INF : x + f; }, [](int f, int g) { return f + g; }, []() { return 0; }> seg(init);
  sort(rall(add_seg));
  ll ans = seg.all_prod();
  rep(r, k) {
    while (add_seg.size() && get<0>(add_seg.back()) == r) {
      auto [_, v, l, r] = add_seg.back();
      add_seg.pop_back();
      seg.apply(vc(l), vc(r), v);
    }
    chmin(ans, seg.all_prod());
  }
  assert(add_seg.empty());
  cout << ans << '\n';
}
0