結果
問題 | No.2809 Sort Query |
ユーザー | silv723 |
提出日時 | 2024-04-21 19:48:29 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,941 bytes |
コンパイル時間 | 5,114 ms |
コンパイル使用メモリ | 298,280 KB |
実行使用メモリ | 33,288 KB |
最終ジャッジ日時 | 2024-07-12 20:56:22 |
合計ジャッジ時間 | 27,824 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | AC | 804 ms
33,288 KB |
testcase_37 | AC | 805 ms
33,156 KB |
testcase_38 | AC | 828 ms
33,156 KB |
testcase_39 | AC | 816 ms
33,284 KB |
testcase_40 | AC | 834 ms
33,156 KB |
testcase_41 | RE | - |
testcase_42 | RE | - |
testcase_43 | RE | - |
testcase_44 | RE | - |
testcase_45 | RE | - |
testcase_46 | RE | - |
testcase_47 | RE | - |
testcase_48 | RE | - |
testcase_49 | RE | - |
testcase_50 | RE | - |
testcase_51 | RE | - |
testcase_52 | RE | - |
testcase_53 | RE | - |
testcase_54 | RE | - |
testcase_55 | RE | - |
testcase_56 | RE | - |
testcase_57 | RE | - |
testcase_58 | RE | - |
testcase_59 | RE | - |
testcase_60 | RE | - |
testcase_61 | RE | - |
testcase_62 | RE | - |
testcase_63 | RE | - |
testcase_64 | RE | - |
testcase_65 | RE | - |
testcase_66 | RE | - |
testcase_67 | RE | - |
testcase_68 | RE | - |
testcase_69 | RE | - |
testcase_70 | RE | - |
ソースコード
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; struct segtree{ int n; vector<int> dat; segtree(int _n):n(_n){ dat.resize(2*n); } void update(int i, int c){ i += n; dat[i] = c; i /= 2; while(i){ dat[i] = dat[2*i] + dat[2*i+1]; i /= 2; } } int sum(int l, int r){ l += n; r += n; int ret = 0; while(l < r){ if(l & 1) ret += dat[l++]; if(r & 1) ret += dat[--r]; l /= 2, r /= 2; } return ret; } }; int main(){ int n, q; scanf("%d%d", &n, &q); assert(1 <= n && n <= 500000 && 1 <= q && q <= 500000); tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> m; segtree ch(n); unordered_map<int, long long> m2; long long check_x = 0; for(int i = 0; i < n; i++){ long long x; scanf("%ld", &x); assert(1 <= x && x <= 1000000000000000000LL); assert(check_x <= x); check_x = x; m.insert(x); } while(q--){ int type; scanf("%d", &type); assert(1 <= type && type <= 3); if(type == 1){ int k; long long x; scanf("%d%ld", &k, &x); assert(1 <= k && k <= n && 1 <= x && x <= 1000000000000000000LL); k--; if(m2.count(k)){ m2[k] = x; }else{ m2[k] = x; ch.update(k, 1); int c = ch.sum(0, k); auto p = m.find_by_order(k - c); m.erase(p); } }else if(type == 2){ for(auto [p, q] : m2){ ch.update(p, 0); m.insert(q); } m2.clear(); }else{ int k; scanf("%d", &k); assert(1 <= k && k <= n); k--; if(m2.count(k)){ printf("%ld", m2[k]); }else{ int c = ch.sum(0, k); auto p = m.find_by_order(k - c); printf("%ld", *p); } } } }