結果
問題 | No.2304 Distinct Elements |
ユーザー | risujiroh |
提出日時 | 2023-05-12 22:56:53 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,297 bytes |
コンパイル時間 | 3,719 ms |
コンパイル使用メモリ | 267,996 KB |
実行使用メモリ | 29,944 KB |
最終ジャッジ日時 | 2024-11-28 19:36:23 |
合計ジャッジ時間 | 110,395 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,624 KB |
testcase_01 | AC | 2 ms
9,472 KB |
testcase_02 | AC | 2 ms
9,472 KB |
testcase_03 | AC | 2 ms
10,624 KB |
testcase_04 | TLE | - |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | AC | 76 ms
29,944 KB |
testcase_10 | AC | 76 ms
28,536 KB |
testcase_11 | AC | 75 ms
27,896 KB |
testcase_12 | AC | 75 ms
29,820 KB |
testcase_13 | AC | 75 ms
29,816 KB |
testcase_14 | AC | 8 ms
8,960 KB |
testcase_15 | AC | 3 ms
8,832 KB |
testcase_16 | AC | 2 ms
10,624 KB |
testcase_17 | AC | 2 ms
10,624 KB |
testcase_18 | AC | 3 ms
9,344 KB |
testcase_19 | AC | 2 ms
10,624 KB |
testcase_20 | AC | 2 ms
9,344 KB |
testcase_21 | AC | 2 ms
10,624 KB |
testcase_22 | AC | 2 ms
9,216 KB |
testcase_23 | AC | 2 ms
10,532 KB |
testcase_24 | AC | 3 ms
8,832 KB |
testcase_25 | AC | 3 ms
10,624 KB |
testcase_26 | AC | 3 ms
9,600 KB |
testcase_27 | AC | 2 ms
9,344 KB |
testcase_28 | AC | 2 ms
10,624 KB |
testcase_29 | TLE | - |
testcase_30 | TLE | - |
testcase_31 | TLE | - |
testcase_32 | AC | 61 ms
28,368 KB |
testcase_33 | AC | 7 ms
10,624 KB |
testcase_34 | AC | 63 ms
28,380 KB |
testcase_35 | AC | 69 ms
29,864 KB |
testcase_36 | AC | 6 ms
9,344 KB |
testcase_37 | TLE | - |
testcase_38 | TLE | - |
testcase_39 | TLE | - |
testcase_40 | TLE | - |
testcase_41 | TLE | - |
testcase_42 | TLE | - |
testcase_43 | TLE | - |
testcase_44 | AC | 59 ms
28,312 KB |
testcase_45 | AC | 43 ms
19,496 KB |
testcase_46 | AC | 35 ms
23,160 KB |
testcase_47 | AC | 10 ms
13,636 KB |
testcase_48 | AC | 10 ms
10,624 KB |
testcase_49 | TLE | - |
testcase_50 | TLE | - |
testcase_51 | TLE | - |
testcase_52 | TLE | - |
testcase_53 | TLE | - |
testcase_54 | TLE | - |
testcase_55 | TLE | - |
testcase_56 | TLE | - |
testcase_57 | TLE | - |
testcase_58 | TLE | - |
testcase_59 | TLE | - |
testcase_60 | AC | 2 ms
5,248 KB |
testcase_61 | AC | 2 ms
9,472 KB |
ソースコード
#if __INCLUDE_LEVEL__ == 0#include <bits/stdc++.h>using namespace std;#undef assert#define assert(expr) (expr) || (__builtin_unreachable(), 0)#include __BASE_FILE__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() const { return lower.top(); }void merge(S s) {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);}while (ssize(upper) < ssize(lower)) {upper.push(lower.top());lower.pop();}while (ssize(lower) < ssize(upper)) {lower.push(upper.top());upper.pop();}}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()) {t.merge(::move(s.back()));s.pop_back();}s.push_back(t);}int64_t ans = 0;for (auto&& e : s) {ans += e.cost();}cout << ans << '\n';}} // namespace} // namespace std::ranges::viewsusing 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 impltemplate <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__