結果
問題 |
No.2304 Distinct Elements
|
ユーザー |
![]() |
提出日時 | 2023-05-13 02:22:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 113 ms / 3,000 ms |
コード長 | 3,504 bytes |
コンパイル時間 | 3,854 ms |
コンパイル使用メモリ | 271,068 KB |
実行使用メモリ | 30,104 KB |
最終ジャッジ日時 | 2024-11-28 22:26:17 |
合計ジャッジ時間 | 8,849 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 58 |
ソースコード
#if __INCLUDE_LEVEL__ == 0 #include <bits/stdc++.h> using namespace std; #undef assert #define assert(expr) (expr) || (__builtin_unreachable(), 0) #include __BASE_FILE__ #define show(...) static_cast<void>(0) namespace std::ranges::views { namespace { struct S { priority_queue<int> lower; priority_queue<int, vector<int>, greater> upper; explicit S(int x) { lower.push(x); } int median() { while (ssize(upper) < ssize(lower)) { upper.push(lower.top()); lower.pop(); } while (ssize(lower) < ssize(upper)) { lower.push(upper.top()); upper.pop(); } return lower.top(); } int size() const { return ssize(lower) + ssize(upper); } void merge(S s) { show(size(), s.size()); while (ssize(s.lower)) { add(s.lower.top()); s.lower.pop(); } while (ssize(s.upper)) { add(s.upper.top()); s.upper.pop(); } } void add(int x) { if (::empty(upper) || x < upper.top()) { lower.push(x); } else { upper.push(x); } } int64_t cost() { int m = median(); int64_t cost = 0; while (ssize(lower)) { cost += abs(lower.top() - m); lower.pop(); } while (ssize(upper)) { cost += abs(upper.top() - m); upper.pop(); } return cost; } }; void solve() { int n; cin >> n; vector<int> a(n); cin >> a; sort(a); for (int i : iota(0, n)) { a[i] -= i; } vector<S> s; for (int e : a) { S t(e); while (ssize(s) && t.median() < s.back().median()) { if (ssize(t) < ssize(s.back())) { swap(t, s.back()); } t.merge(::move(s.back())); s.pop_back(); } s.push_back(::move(t)); } int64_t ans = 0; for (auto&& e : s) { ans += e.cost(); } cout << ans << '\n'; } } // namespace } // namespace std::ranges::views using views::solve; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); } #else // __INCLUDE_LEVEL__ namespace std { template <class T1, class T2> istream& operator>>(istream& is, pair<T1, T2>& p) { return is >> p.first >> p.second; } template <class... Ts> istream& operator>>(istream& is, tuple<Ts...>& t) { return apply([&is](auto&... xs) -> istream& { return (is >> ... >> xs); }, t); } template <class R, enable_if_t<!is_convertible_v<R, string>>* = nullptr> auto operator>>(istream& is, R&& r) -> decltype(is >> *begin(r)) { for (auto&& e : r) { is >> e; } return is; } template <class T1, class T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << p.first << ' ' << p.second; } template <class... Ts> ostream& operator<<(ostream& os, const tuple<Ts...>& t) { auto f = [&os](const auto&... xs) -> ostream& { [[maybe_unused]] auto sep = ""; ((os << exchange(sep, " ") << xs), ...); return os; }; return apply(f, t); } namespace impl { template <class R> constexpr int n_dims(char) { return 0; } template <class R> constexpr auto n_dims(int) -> decltype(begin(declval<R>()), 0) { return n_dims<decltype(*begin(declval<R>()))>(0) + 1; } } // namespace impl template <class R, enable_if_t<!is_convertible_v<R, string_view>>* = nullptr> auto operator<<(ostream& os, R&& r) -> decltype(os << *begin(r)) { static constexpr int D = impl::n_dims<R>(0); static const string SEP = 1 < D ? string(D - 1, '\n') : " "; string sep; for (auto&& e : r) { os << exchange(sep, SEP) << e; } return os; } } // namespace std #endif // __INCLUDE_LEVEL__