結果
問題 | No.2809 Sort Query |
ユーザー | Aeren |
提出日時 | 2024-07-12 22:24:27 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 10,976 bytes |
コンパイル時間 | 4,045 ms |
コンパイル使用メモリ | 283,884 KB |
実行使用メモリ | 75,096 KB |
最終ジャッジ日時 | 2024-07-12 22:25:10 |
合計ジャッジ時間 | 42,165 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | AC | 500 ms
73,464 KB |
testcase_37 | AC | 522 ms
73,152 KB |
testcase_38 | AC | 528 ms
73,380 KB |
testcase_39 | AC | 525 ms
73,628 KB |
testcase_40 | AC | 522 ms
73,360 KB |
testcase_41 | AC | 317 ms
38,940 KB |
testcase_42 | AC | 321 ms
40,060 KB |
testcase_43 | AC | 321 ms
39,416 KB |
testcase_44 | AC | 317 ms
39,116 KB |
testcase_45 | AC | 315 ms
39,284 KB |
testcase_46 | AC | 253 ms
39,560 KB |
testcase_47 | AC | 247 ms
38,628 KB |
testcase_48 | AC | 263 ms
38,864 KB |
testcase_49 | AC | 253 ms
39,600 KB |
testcase_50 | AC | 251 ms
38,884 KB |
testcase_51 | WA | - |
testcase_52 | WA | - |
testcase_53 | WA | - |
testcase_54 | WA | - |
testcase_55 | WA | - |
testcase_56 | WA | - |
testcase_57 | WA | - |
testcase_58 | WA | - |
testcase_59 | WA | - |
testcase_60 | WA | - |
testcase_61 | WA | - |
testcase_62 | WA | - |
testcase_63 | WA | - |
testcase_64 | WA | - |
testcase_65 | WA | - |
testcase_66 | WA | - |
testcase_67 | WA | - |
testcase_68 | WA | - |
testcase_69 | WA | - |
testcase_70 | AC | 2 ms
6,940 KB |
ソースコード
// #include <bits/allocator.h> // Temp fix for gcc13 global pragma // #pragma GCC target("avx2,bmi2,popcnt,lzcnt") // #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> // #include <x86intrin.h> using namespace std; #if __cplusplus >= 202002L using namespace numbers; #endif #ifdef LOCAL #include "Debug.h" #else #define debug_endl() 42 #define debug(...) 42 #define debug2(...) 42 #define debugbin(...) 42 #endif template<bool HAS_QUERY, bool HAS_UPDATE, class T, class U, class F1, class F2, class F3> struct segment_tree_base{ static_assert(HAS_QUERY || HAS_UPDATE); #define ifQ if constexpr(HAS_QUERY) #define ifU if constexpr(HAS_UPDATE) int n, size, log; vector<T> data; vector<U> data_action; F1 TT; // monoid operation (always adjacent) T T_id; // monoid identity F2 UU; // monoid operation (superset, subset) U U_id; // monoid identity F3 UT; // action of U on T (superset, subset) // O(n) segment_tree_base(F1 TT, T T_id, F2 UU, U U_id, F3 UT): TT(TT), T_id(T_id), UU(UU), U_id(U_id), UT(UT){ } segment_tree_base &operator=(const segment_tree_base &seg){ n = seg.n; size = seg.size; log = seg.log; data = seg.data; data_action = seg.data_action; } // O(1) friend void swap(segment_tree_base &x, segment_tree_base &y){ swap(x.n, y.n); swap(x.size, y.size); swap(x.log, y.log); swap(x.data, y.data); swap(x.data_action, y.data_action); } // O(n) void build(int n){ assert(n >= 0); this->n = n; size = 1; while(size < n) size <<= 1; log = __lg(size); ifQ data.assign(size << 1, T_id); ifU data_action.assign(HAS_QUERY ? size : size << 1, U_id); } // O(n) void build(int n, T x){ static_assert(HAS_QUERY); assert(n >= 0); this->n = n; size = 1; while(size < n) size <<= 1; log = __lg(size); data.assign(size << 1, T_id); fill(data.begin() + size, data.begin() + size + n, x); for(auto i = size - 1; i >= 1; -- i) refresh(i); ifU data_action.assign(size, U_id); } // O(n) template<class V> void build(const vector<V> &a){ static_assert(HAS_QUERY); n = (int)a.size(); size = 1; while(size < n) size <<= 1; log = __lg(size); data.assign(size << 1, T_id); copy(a.begin(), a.end(), data.begin() + size); for(auto i = size - 1; i >= 1; -- i) refresh(i); ifU data_action.assign(size, U_id); } // O(n) void build_action(int n){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(n >= 0); build(n); } // O(n) void build_action(int n, U f){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(n >= 0); this->n = n; size = 1; while(size < n) size <<= 1; log = __lg(size); data_action.assign(size << 1, U_id); fill(data_action.begin() + size, data_action.begin() + size + n, f); } // O(n) template<class V> void build_action(const vector<V> &a){ static_assert(!HAS_QUERY && HAS_UPDATE); n = (int)a.size(); size = 1; while(size < n) size <<= 1; log = __lg(size); data_action.assign(size << 1, U_id); copy(a.begin(), a.end(), data_action.begin() + size); } // O(1) void refresh(int u){ static_assert(HAS_QUERY); data[u] = TT(data[u << 1], data[u << 1 | 1]); } // O(1) void apply(int u, U f){ static_assert(HAS_UPDATE); ifQ data[u] = UT(f, data[u]); if(!HAS_QUERY || u < size) data_action[u] = UU(f, data_action[u]); } // O(1) void push(int u){ static_assert(HAS_UPDATE); apply(u << 1, data_action[u]), apply(u << 1 | 1, data_action[u]); data_action[u] = U_id; } // O(log(n)) if HAS_UPDATE, O(1) otherwise. T query(int p){ static_assert(HAS_QUERY); assert(0 <= p && p < n); p += size; ifU for(auto i = log; i >= 1; -- i) push(p >> i); return data[p]; } // O(log(n)) U query_action(int p){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(0 <= p && p < n); p += size; ifU for(auto i = log; i >= 1; -- i) push(p >> i); return data_action[p]; } // O(log(n)) T query(int ql, int qr){ static_assert(HAS_QUERY); assert(0 <= ql && ql <= qr && qr <= n); if(ql == qr) return T_id; ql += size, qr += size; ifU for(auto i = log; i >= 1; -- i){ if(ql >> i << i != ql) push(ql >> i); if(qr >> i << i != qr) push(qr >> i); } T res_left = T_id, res_right = T_id; for(; ql < qr; ql >>= 1, qr >>= 1){ if(ql & 1) res_left = TT(res_left, data[ql ++]); if(qr & 1) res_right = TT(data[-- qr], res_right); } return TT(res_left, res_right); } // O(1) T query_all() const{ static_assert(HAS_QUERY); return data[1]; } // O(n) vector<T> to_array(){ static_assert(HAS_QUERY); ifU for(auto u = 1; u < size; ++ u) push(u); return vector<T>(data.begin() + size, data.begin() + size + n); } // O(n) vector<U> to_array_of_updates(){ static_assert(!HAS_QUERY && HAS_UPDATE); for(auto u = 1; u < size; ++ u) push(u); return vector<U>(data_action.begin() + size, data_action.begin() + size + n); } // O(log(n)) void set(int p, T x){ static_assert(HAS_QUERY); assert(0 <= p && p < n); p += size; ifU for(auto i = log; i >= 1; -- i) push(p >> i); data[p] = x; for(auto i = 1; i <= log; ++ i) refresh(p >> i); } // O(log(n)) void set_action(int p, U f){ static_assert(!HAS_QUERY && HAS_UPDATE); assert(0 <= p && p < n); p += size; for(auto i = log; i >= 1; -- i) push(p >> i); data_action[p] = f; } // O(log(n)) void update(int p, U f){ static_assert(HAS_UPDATE); assert(0 <= p && p < n); p += size; for(auto i = log; i >= 1; -- i) push(p >> i); ifQ{ data[p] = UT(f, data[p]); for(auto i = 1; i <= log; ++ i) refresh(p >> i); } else data_action[p] = UU(f, data_action[p]); } // O(log(n)) void update(int ql, int qr, U f){ static_assert(HAS_UPDATE); assert(0 <= ql && ql <= qr && qr <= n); if(ql == qr) return; ql += size, qr += size; for(auto i = log; i >= 1; -- i){ if(ql >> i << i != ql) push(ql >> i); if(qr >> i << i != qr) push(qr >> i); } int _ql = ql, _qr = qr; for(; ql < qr; ql >>= 1, qr >>= 1){ if(ql & 1) apply(ql ++, f); if(qr & 1) apply(-- qr, f); } ql = _ql, qr = _qr; ifQ for(auto i = 1; i <= log; ++ i){ if(ql >> i << i != ql) refresh(ql >> i); if(qr >> i << i != qr) refresh(qr >> i); } } void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){ static_assert(HAS_QUERY && HAS_UPDATE); assert(0 <= ql && ql <= qr && qr <= n); if(ql == qr) return; ql += size, qr += size; for(auto i = log; i >= 1; -- i){ if(ql >> i << i != ql) push(ql >> i); if(qr >> i << i != qr) push(qr >> i); } auto recurse = [&](auto self, int u)->void{ if(exit_rule(data[u])) return; if(enter_rule(data[u])){ apply(u, update_rule(data[u])); return; } push(u); self(self, u << 1), self(self, u << 1 | 1); refresh(u); }; int _ql = ql, _qr = qr; for(; ql < qr; ql >>= 1, qr >>= 1){ if(ql & 1) recurse(recurse, ql ++); if(qr & 1) recurse(recurse, -- qr); } ql = _ql, qr = _qr; for(auto i = 1; i <= log; ++ i){ if(ql >> i << i != ql) refresh(ql >> i); if(qr >> i << i != qr) refresh(qr >> i); } } // pred(sum[ql, r)) is T, T, ..., T, F, F, ..., F // Returns max r with T // O(log(n)) int max_pref(int ql, auto pred){ static_assert(HAS_QUERY); assert(0 <= ql && ql <= n && pred(T_id)); if(ql == n) return n; ql += size; ifU for(auto i = log; i >= 1; -- i) push(ql >> i); T sum = T_id; do{ while(~ql & 1) ql >>= 1; if(!pred(TT(sum, data[ql]))){ while(ql < size){ ifU push(ql); ql = ql << 1; if(pred(TT(sum, data[ql]))) sum = TT(sum, data[ql ++]); } return ql - size; } sum = TT(sum, data[ql]); ++ ql; }while((ql & -ql) != ql); return n; } // pred(sum[l, qr)) is F, F, ..., F, T, T, ..., T // Returns min l with T // O(log(n)) int max_suff(int qr, auto pred){ static_assert(HAS_QUERY); assert(0 <= qr && qr <= n && pred(T_id)); if(qr == 0) return 0; qr += size; ifU for(auto i = log; i >= 1; -- i) push(qr - 1 >> i); T sum = T_id; do{ -- qr; while(qr > 1 && qr & 1) qr >>= 1; if(!pred(TT(data[qr], sum))){ while(qr < size){ ifU push(qr); qr = qr << 1 | 1; if(pred(TT(data[qr], sum))) sum = TT(data[qr --], sum); } return qr + 1 - size; } sum = TT(data[qr], sum); }while((qr & -qr) != qr); return 0; } template<class output_stream> friend output_stream &operator<<(output_stream &out, segment_tree_base<HAS_QUERY, HAS_UPDATE, T, U, F1, F2, F3> seg){ out << "{"; for(auto i = 0; i < seg.n; ++ i){ ifQ out << seg.query(i); else out << seg.query_action(i); if(i != seg.n - 1) out << ", "; } return out << '}'; } #undef ifQ #undef ifU }; // Supports query template<class T, class F> auto make_Q_segment_tree(F TT, T T_id){ using U = int; auto _UU = [&](U, U)->U{ return U{}; }; auto _UT = [&](U, T)->T{ return T{}; }; return segment_tree_base<true, false, T, U, F, decltype(_UU), decltype(_UT)>(TT, T_id, _UU, U{}, _UT); } // Supports update template<class U, class F> auto make_U_segment_tree(F UU, U U_id){ using T = int; auto _TT = [&](T, T)->T{ return T{}; }; auto _UT = [&](U, T)->T{ return T{}; }; return segment_tree_base<false, true, T, U, decltype(_TT), F, decltype(_UT)>(_TT, T{}, UU, U_id, _UT); } // Supports query and update template<class T, class U, class F1, class F2, class F3> auto make_QU_segment_tree(F1 TT, T T_id, F2 UU, U U_id, F3 UT){ return segment_tree_base<true, true, T, U, F1, F2, F3>(TT, T_id, UU, U_id, UT); } int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int n, qn; cin >> n >> qn; vector<long long> a(n); copy_n(istream_iterator<long long>(cin), n, a.begin()); vector<pair<long long, int>> cmpr; for(auto i = 0; i < n; ++ i){ cmpr.push_back({a[i], i}); } vector<array<long long, 3>> q(qn); for(auto i = n; auto &[type, p, x]: q){ cin >> type; if(type != 2){ cin >> p, -- p; if(type == 1){ cin >> x; cmpr.push_back({x, i ++}); } } } ranges::sort(cmpr); cmpr.erase(ranges::unique(cmpr).begin(), cmpr.end()); using T = pair<int, long long>; // cnt, maxv T T_id{0, -1}; auto TT = [&](const T &x, const T &y)->T{ return {x.first + y.first, max(x.second, y.second)}; }; auto seg = make_Q_segment_tree(TT, T_id); vector<T> init((int)cmpr.size(), T_id); auto index = [&](long long x, int i)->int{ return ranges::lower_bound(cmpr, pair{x, i}) - cmpr.begin(); }; for(auto i = 0; i < n; ++ i){ init[index(a[i], i)] = {1, a[i]}; } seg.build(init); map<int, int> update; for(int i = n; auto [type, p, x]: q){ if(type == 1){ update[p] = index(x, i ++); } else if(type == 2){ for(auto [p, v]: update){ auto w = seg.max_pref(0, [&](auto pref){ return pref.first <= p; }); seg.set(w, T_id); seg.set(v, T{1, cmpr[v].first}); } update.clear(); } else{ if(update.contains(p)){ cout << update[p] << "\n"; } else{ auto x = seg.max_pref(0, [&](auto pref){ return pref.first <= p; }); cout << seg.query(x).second << "\n"; } } } return 0; } /* */