結果
問題 | No.2627 Unnatural Pitch |
ユーザー | tokusakurai |
提出日時 | 2024-02-09 23:45:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 494 ms / 4,000 ms |
コード長 | 13,347 bytes |
コンパイル時間 | 2,395 ms |
コンパイル使用メモリ | 217,148 KB |
実行使用メモリ | 37,056 KB |
最終ジャッジ日時 | 2024-09-28 16:40:57 |
合計ジャッジ時間 | 8,064 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 12 ms
7,928 KB |
testcase_03 | AC | 2 ms
6,816 KB |
testcase_04 | AC | 184 ms
31,360 KB |
testcase_05 | AC | 182 ms
32,056 KB |
testcase_06 | AC | 83 ms
20,440 KB |
testcase_07 | AC | 66 ms
15,316 KB |
testcase_08 | AC | 96 ms
18,084 KB |
testcase_09 | AC | 193 ms
27,304 KB |
testcase_10 | AC | 203 ms
31,484 KB |
testcase_11 | AC | 3 ms
6,820 KB |
testcase_12 | AC | 3 ms
6,816 KB |
testcase_13 | AC | 2 ms
6,816 KB |
testcase_14 | AC | 4 ms
6,820 KB |
testcase_15 | AC | 3 ms
6,820 KB |
testcase_16 | AC | 465 ms
34,372 KB |
testcase_17 | AC | 494 ms
37,056 KB |
testcase_18 | AC | 442 ms
32,976 KB |
testcase_19 | AC | 477 ms
35,424 KB |
testcase_20 | AC | 146 ms
15,204 KB |
testcase_21 | AC | 202 ms
19,328 KB |
testcase_22 | AC | 359 ms
29,368 KB |
testcase_23 | AC | 194 ms
19,224 KB |
testcase_24 | AC | 270 ms
21,064 KB |
testcase_25 | AC | 258 ms
22,696 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (n); i++) #define per(i, n) for (int i = (n)-1; i >= 0; i--) #define rep2(i, l, r) for (int i = (l); i < (r); i++) #define per2(i, l, r) for (int i = (r)-1; i >= (l); i--) #define each(e, v) for (auto &e : v) #define MM << " " << #define pb push_back #define eb emplace_back #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sz(x) (int)x.size() using ll = long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; template <typename T> using minheap = priority_queue<T, vector<T>, greater<T>>; template <typename T> using maxheap = priority_queue<T>; template <typename T> bool chmax(T &x, const T &y) { return (x < y) ? (x = y, true) : false; } template <typename T> bool chmin(T &x, const T &y) { return (x > y) ? (x = y, true) : false; } template <typename T> int flg(T x, int i) { return (x >> i) & 1; } int pct(int x) { return __builtin_popcount(x); } int pct(ll x) { return __builtin_popcountll(x); } int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int botbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int botbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template <typename T> void print(const vector<T> &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' '); if (v.empty()) cout << '\n'; } template <typename T> void printn(const vector<T> &v, T x = 0) { int n = v.size(); for (int i = 0; i < n; i++) cout << v[i] + x << '\n'; } template <typename T> int lb(const vector<T> &v, T x) { return lower_bound(begin(v), end(v), x) - begin(v); } template <typename T> int ub(const vector<T> &v, T x) { return upper_bound(begin(v), end(v), x) - begin(v); } template <typename T> void rearrange(vector<T> &v) { sort(begin(v), end(v)); v.erase(unique(begin(v), end(v)), end(v)); } template <typename T> vector<int> id_sort(const vector<T> &v, bool greater = false) { int n = v.size(); vector<int> ret(n); iota(begin(ret), end(ret), 0); sort(begin(ret), end(ret), [&](int i, int j) { return greater ? v[i] > v[j] : v[i] < v[j]; }); return ret; } template <typename T> void reorder(vector<T> &a, const vector<int> &ord) { int n = a.size(); vector<T> b(n); for (int i = 0; i < n; i++) b[i] = a[ord[i]]; swap(a, b); } template <typename T> T floor(T x, T y) { assert(y != 0); if (y < 0) x = -x, y = -y; return (x >= 0 ? x / y : (x - y + 1) / y); } template <typename T> T ceil(T x, T y) { assert(y != 0); if (y < 0) x = -x, y = -y; return (x >= 0 ? (x + y - 1) / y : x / y); } template <typename S, typename T> pair<S, T> operator+(const pair<S, T> &p, const pair<S, T> &q) { return make_pair(p.first + q.first, p.second + q.second); } template <typename S, typename T> pair<S, T> operator-(const pair<S, T> &p, const pair<S, T> &q) { return make_pair(p.first - q.first, p.second - q.second); } template <typename S, typename T> istream &operator>>(istream &is, pair<S, T> &p) { S a; T b; is >> a >> b; p = make_pair(a, b); return is; } template <typename S, typename T> ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << p.first << ' ' << p.second; } struct io_setup { io_setup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); } } io_setup; constexpr int inf = (1 << 30) - 1; constexpr ll INF = (1LL << 60) - 1; // constexpr int MOD = 1000000007; constexpr int MOD = 998244353; template <typename T> struct Binary_Indexed_Tree { vector<T> bit; const int n; Binary_Indexed_Tree(const vector<T> &v) : n((int)v.size()) { bit.resize(n + 1); copy(begin(v), end(v), begin(bit) + 1); build(); } Binary_Indexed_Tree(int n, T x = 0) : Binary_Indexed_Tree(vector<T>(n, x)) {} void set(int i, const T &x) { bit[i + 1] = x; } void build() { for (int a = 2; a <= n; a <<= 1) { for (int b = a; b <= n; b += a) bit[b] += bit[b - a / 2]; } } void add(int i, const T &x) { for (i++; i <= n; i += (i & -i)) bit[i] += x; } void change(int i, const T &x) { add(i, x - query(i, i + 1)); } T sum(int i) const { i = min(i, n); if (i <= 0) return 0; T ret = 0; for (; i > 0; i -= (i & -i)) ret += bit[i]; return ret; } T query(int l, int r) const { l = max(l, 0), r = min(r, n); if (l >= r) return 0; return sum(r) - sum(l); } T operator[](int i) const { return query(i, i + 1); } // v[0]+...+v[r] >= x を満たす最小の r (なければ n) int lower_bound(T x) const { int ret = 0; for (int k = 31 - __builtin_clz(n); k >= 0; k--) { if (ret + (1 << k) <= n && bit[ret + (1 << k)] < x) x -= bit[ret += (1 << k)]; } return ret; } // v[0]+...+v[r] > x を満たす最小の r (なければ n) int upper_bound(T x) const { int ret = 0; for (int k = 31 - __builtin_clz(n); k >= 0; k--) { if (ret + (1 << k) <= n && bit[ret + (1 << k)] <= x) x -= bit[ret += (1 << k)]; } return ret; } }; template <typename T> struct Range_Add_Range_Sum { Binary_Indexed_Tree<T> bit0, bit1; const int n; Range_Add_Range_Sum(const vector<T> &v) : n(v.size()), bit0(v), bit1(v.size(), 0) {} Range_Add_Range_Sum(int n, const T &x) : Range_Add_Range_Sum(vector<T>(n, x)) {} void add(int l, int r, const T &x) { l = max(l, 0), r = min(r, n); if (l >= r) return; bit0.add(l, -x * T(l)), bit1.add(l, x); if (r < n) bit0.add(r, x * T(r)), bit1.add(r, -x); } T sum(int i) const { i = min(i, n); if (i < 0) return 0; return bit0.sum(i) + bit1.sum(i) * T(i); } T query(int l, int r) const { l = max(l, 0), r = min(r, n); if (l >= r) return 0; return sum(r) - sum(l); } }; template <typename T> struct Slope_Trick { priority_queue<T> l; priority_queue<T, vector<T>, greater<T>> r; const T INF_T = numeric_limits<T>::max() / 2; T add_l, add_r; T min_f = 0; // f(x) = 0 で初期化 Slope_Trick() : add_l(0), add_r(0) { l.push(-INF_T); r.push(INF_T); } T get_min() const { return min_f; }; void add_constant(const T &c) { min_f += c; }; // f(x) += max(-x+a, 0) void add_line_left(const T &a) { if (a > r.top() + add_r) { min_f += -(r.top() + add_r) + a; l.push(r.top() + add_r - add_l); r.pop(); r.push(a - add_r); } else { l.push(a - add_l); } } // f(x) += max(x-a, 0) void add_line_right(const T &a) { if (a < l.top() + add_l) { min_f += (l.top() + add_l) - a; r.push(l.top() + add_l - add_r); l.pop(); l.push(a - add_l); } else { r.push(a - add_r); } } // f(x) += |x-a| void add_abs(const T &a) { add_line_left(a); add_line_right(a); } // f(x) <- min{f(y) | y <= x} void left_min() { while ((int)r.size() > 1) r.pop(); } // f(x) <- min{f(y) | y >= x} void right_min() { while ((int)l.size() > 1) l.pop(); } // f(x) <- min{f(y) | x-b <= y <= x-a} void slide_min(const T &a, const T &b) { assert(a <= b); add_l += a; add_r += b; } // f(x) <- f(x-a) void shift(const T &a) { add_l += a; add_r += a; } // f(x) を入手 (ただし、l と r は破壊される) T get(const T &x) { T ret = min_f; while (!l.empty()) { ret += max(T(0), -x + (l.top() + add_l)); l.pop(); } while (!r.empty()) { ret += max(T(0), x - (r.top() + add_r)); r.pop(); } return ret; } }; void solve() { ll N, K, LEFT, RIGHT; cin >> N >> K >> LEFT >> RIGHT; vector<ll> a(N); rep(i, N) cin >> a[i]; ll D = RIGHT - LEFT; vector<vector<ll>> ids(K); rep(i, N) ids[a[i] % K].eb(a[i]); vector<ll> xs; each(e, a) { xs.eb(ceil(e - D, K)); xs.eb(ceil(e - D - (K - 1), K)); xs.eb(floor(e, K)); xs.eb(floor(e - (K - 1), K)); } rearrange(xs); int L = sz(xs); Binary_Indexed_Tree<ll> b_cnt(L, 0), b_plus(L, 0); ll sum = 0; auto erase = [&](ll l, int type = 0) { int t = lb(xs, l); assert(xs[t] == l); b_cnt.add(t, -1); b_plus.add(t, -l); if (type) sum -= l; }; auto insert = [&](ll l, int type = 0) { int t = lb(xs, l); assert(xs[t] == l); b_cnt.add(t, 1); b_plus.add(t, l); if (type) sum += l; }; auto get_ans = [&]() { // for (int i = 0; i < L; i++) cout << b_cnt[i] << (i == L - 1 ? '\n' : ' '); int t = b_cnt.lower_bound(N); return -b_plus.query(0, t + 1) + b_cnt.query(0, t + 1) * xs[t] - xs[t] * N + sum; // ll l = b_cnt.query(0, t) * xs[t] - b_plus.query(0, t); // ll r = b_plus.query(t, L) - b_cnt.query(t, L) * xs[t]; // cout << "! " << t MM L MM l MM r MM xs[t] MM sum << endl; // return l + r - xs[t] * N + sum; }; rep(i, N) { insert(ceil(a[i] - D, K), 1); insert(floor(a[i], K)); } ll ans = get_ans(); // print(xs); rep2(j, 1, K) { { int m = (j - 1) % K; if (m < 0) m += K; each(e, ids[m]) { erase(floor(e - (j - 1), K)); insert(floor(e - j, K)); } } { int m = (D + j) % K; if (m < 0) m += K; each(e, ids[m]) { erase(ceil(e - D - (j - 1), K), 1); insert(ceil(e - D - j, K), 1); } } chmin(ans, get_ans()); } cout << ans << '\n'; // auto erase = [&](int i, int j) { // for (auto &e : ids[i]) { // ll l = ceil(e - D - j, K); // ll r = ceil(e - j, K); // } // }; // auto insert = [&](int i, int j) { // for (auto &e : ids[i]) { // ll l = ceil(e - D - j, K); // ll r = ceil(e - j, K); // } // }; // auto get_upper = [&]() { // vector<ll> ret(N, 0); // Binary_Indexed_Tree<ll> bit(K, 0); // queue<ll> que; // que.emplace(a[N - 1]); // ll ans = 0; // per(i, N - 1) { // ll d = a[i + 1] - a[i]; // ans += bit.query(0, K) * (d / K); // d %= K; // ll r = (a[i + 1] + D) % K + 1; // ll l = r - d; // if (0 <= l) { // ans += bit.query(l, r); // } else { // ans += bit.query(K + l, K); // ans += bit.query(0, r); // } // while (!empty(que)) { // ll x = que.front(); // if (x > a[i] + D) { // ans += ceil(x - (a[i] + D), K); // bit.add(x % K, 1); // que.pop(); // } else { // break; // } // } // ret[i] = ans; // que.emplace(a[i]); // } // return ret; // }; // auto get_lower = [&]() { // vector<ll> ret(N, 0); // Binary_Indexed_Tree<ll> bit(K, 0); // queue<ll> que; // que.emplace(a[0]); // ll ans = 0; // rep2(i, 1, N) { // ll d = a[i] - a[i - 1]; // ans += bit.query(0, K) * (d / K); // d %= K; // ll l = a[i - 1] % K; // ll r = l + d; // if (r <= K) { // ans += bit.query(l, r); // } else { // ans += bit.query(l, K); // ans += bit.query(0, r - K); // } // while (!empty(que)) { // ll x = que.front(); // if (x < a[i]) { // ans += ceil(a[i] - x, K); // bit.add(x % K, 1); // que.pop(); // } else { // break; // } // } // ret[i] = ans; // que.emplace(a[i]); // } // return ret; // }; // auto up = get_upper(), lo = get_lower(); // ll ans = INF; // vector<ll> nup(N, 0), nlo(N, 0); // rep(i, N) { // rep2(j, i + 1, N) { // if (a[j] > a[i] + D) nup[i] += ceil(a[j] - a[i] - D, K); // } // rep(j, i) { // if (a[j] < a[i]) nlo[i] += ceil(a[i] - a[j], K); // } // } // print(a), print(up), print(nup), print(lo), print(nlo); // rep(i, N) chmin(ans, up[i] + lo[i]); // cout << ans << '\n'; } int main() { int T = 1; // cin >> T; while (T--) solve(); }