結果
問題 | No.2304 Distinct Elements |
ユーザー | t98slider |
提出日時 | 2023-05-13 23:06:57 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,090 bytes |
コンパイル時間 | 1,825 ms |
コンパイル使用メモリ | 182,892 KB |
実行使用メモリ | 105,456 KB |
最終ジャッジ日時 | 2023-08-19 19:12:14 |
合計ジャッジ時間 | 17,472 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 322 ms
26,124 KB |
testcase_05 | AC | 323 ms
26,112 KB |
testcase_06 | AC | 321 ms
26,160 KB |
testcase_07 | AC | 333 ms
26,056 KB |
testcase_08 | AC | 342 ms
26,196 KB |
testcase_09 | AC | 275 ms
24,960 KB |
testcase_10 | AC | 261 ms
24,856 KB |
testcase_11 | AC | 266 ms
24,912 KB |
testcase_12 | AC | 269 ms
24,856 KB |
testcase_13 | AC | 284 ms
24,832 KB |
testcase_14 | AC | 3 ms
4,380 KB |
testcase_15 | AC | 2 ms
4,376 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,376 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 1 ms
4,380 KB |
testcase_21 | AC | 2 ms
4,384 KB |
testcase_22 | AC | 1 ms
4,376 KB |
testcase_23 | AC | 2 ms
4,376 KB |
testcase_24 | AC | 1 ms
4,380 KB |
testcase_25 | AC | 2 ms
4,380 KB |
testcase_26 | AC | 2 ms
4,380 KB |
testcase_27 | AC | 1 ms
4,376 KB |
testcase_28 | AC | 2 ms
4,380 KB |
testcase_29 | AC | 239 ms
20,336 KB |
testcase_30 | AC | 19 ms
4,500 KB |
testcase_31 | AC | 194 ms
17,408 KB |
testcase_32 | AC | 206 ms
20,148 KB |
testcase_33 | AC | 17 ms
4,540 KB |
testcase_34 | AC | 215 ms
20,692 KB |
testcase_35 | AC | 238 ms
22,916 KB |
testcase_36 | AC | 14 ms
4,380 KB |
testcase_37 | AC | 97 ms
9,956 KB |
testcase_38 | AC | 323 ms
25,620 KB |
testcase_39 | AC | 325 ms
26,072 KB |
testcase_40 | AC | 205 ms
18,592 KB |
testcase_41 | AC | 104 ms
11,092 KB |
testcase_42 | AC | 315 ms
26,160 KB |
testcase_43 | AC | 341 ms
26,112 KB |
testcase_44 | AC | 190 ms
18,860 KB |
testcase_45 | AC | 224 ms
16,568 KB |
testcase_46 | AC | 157 ms
13,500 KB |
testcase_47 | AC | 2 ms
4,380 KB |
testcase_48 | AC | 3 ms
4,376 KB |
testcase_49 | AC | 336 ms
26,056 KB |
testcase_50 | AC | 337 ms
26,124 KB |
testcase_51 | AC | 329 ms
26,296 KB |
testcase_52 | AC | 351 ms
26,640 KB |
testcase_53 | AC | 334 ms
28,476 KB |
testcase_54 | AC | 341 ms
26,912 KB |
testcase_55 | AC | 344 ms
26,924 KB |
testcase_56 | AC | 342 ms
27,224 KB |
testcase_57 | WA | - |
testcase_58 | AC | 332 ms
26,140 KB |
testcase_59 | AC | 844 ms
44,004 KB |
testcase_60 | AC | 2 ms
4,376 KB |
testcase_61 | AC | 1 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> struct median_priority_queue { std::priority_queue<T> pqL; std::priority_queue<T, std::vector<T>, std::greater<T>> pqR; median_priority_queue() { //pqL.emplace(std::numeric_limits<T>::min()); //pqR.emplace(std::numeric_limits<T>::max()); } void push(T v){ if(!pqL.empty() && v < pqL.top()) pqL.emplace(v); else pqR.emplace(v); update(); } T get(){ return pqR.top(); } int size(){ return int(pqL.size() + pqR.size()); } void update(){ while(pqL.size() + 2 <= pqR.size()){ pqL.emplace(pqR.top()); pqR.pop(); } while(pqL.size() > pqR.size()){ pqR.emplace(pqL.top()); pqL.pop(); } } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n), b(n), parent(n); vector<median_priority_queue<int>> pq(n); for(auto &&v : a) cin >> v; sort(a.begin(), a.end()); iota(parent.begin(), parent.end(), 0); function<int(int)> leader = [&](int v){ return v == parent[v] ? v : parent[v] = leader(parent[v]); }; auto merge = [&](int i, int j){ if(pq[i].size() < pq[j].size()){ swap(pq[i], pq[j]); swap(i, j); } parent[j] = i; auto &tmp = pq[j].pqR; while(!tmp.empty()){ pq[i].push(tmp.top()); tmp.pop(); } auto &tmp2 = pq[j].pqL; while(!tmp2.empty()){ pq[i].push(tmp2.top()); tmp2.pop(); } }; stack<int> st; for(int i = 0; i < n; i++){ b[i] = a[i] - i; pq[i].push(b[i]); st.emplace(i); } for(int i = 0; i + 1 < n; i++){ if(b[i] == b[i + 1]) merge(i, i + 1); } while(st.size() >= 2){ int i = leader(st.top()); st.pop(); int j = leader(st.top()); if(i == j) continue; if(pq[j].get() > pq[i].get()) merge(i, j); } for(int j = 0; j < 30; j++){ st.pop(); for(int i = 0; i < n; i++){ st.emplace(i); } while(st.size() >= 2){ int i = leader(st.top()); st.pop(); int j = leader(st.top()); if(i == j) continue; if(pq[j].get() >= pq[i].get()) merge(i, j); } } for(int j = 0; j < 60; j++){ for(int i = 0; i + 1 < n; i++){ int u = leader(i), v = leader(i + 1); if(u == v) continue; if(pq[u].get() >= pq[v].get()) merge(u, v); } } for(int j = 0; j < 30; j++){ st.pop(); for(int i = 0; i < n; i++){ st.emplace(i); } while(st.size() >= 2){ int i = leader(st.top()); st.pop(); int j = leader(st.top()); if(i == j) continue; if(pq[j].get() >= pq[i].get()) merge(i, j); } } ll ans = 0; for(int i = 0; i < n; i++){ ans += abs(b[i] - pq[parent[leader(i)]].get()); } cout << ans << '\n'; }