結果
問題 |
No.2809 Sort Query
|
ユーザー |
![]() |
提出日時 | 2024-07-12 22:11:08 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,283 ms / 2,000 ms |
コード長 | 4,119 bytes |
コンパイル時間 | 4,902 ms |
コンパイル使用メモリ | 306,820 KB |
実行使用メモリ | 32,584 KB |
最終ジャッジ日時 | 2024-07-12 22:12:38 |
合計ジャッジ時間 | 81,654 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 71 |
ソースコード
#if __INCLUDE_LEVEL__ == 0 #include __BASE_FILE__ namespace { struct S { mutable Int v; Int id; friend auto operator<=>(const S&, const S&) = default; }; void Solve() { Int n, q; Scan(n, q); TreeSet<S> s; for (Int i : Rep(n)) { s.insert({-1, i}); } for (Int i : Rep(n)) { Int a; Scan(a); s.find_by_order(i)->v = a; } std::vector<Int> v(n); std::iota(v.begin(), v.end(), 0); while (q--) { Int t; Scan(t); if (t == 1) { Int k, x; Scan(k, x); --k; s.find_by_order(k)->v = x; v.push_back(k); } else if (t == 2) { ranges::sort(v); v.resize(Sz(v) - Sz(ranges::unique(v))); std::vector<S> tmp; for (Int k : Rev(v)) { auto it = s.find_by_order(k); tmp.push_back(*it); s.erase(it); } ranges::for_each(tmp, $(s.insert($1))); v.clear(); } else { Int k; Scan(k); --k; Print(s.find_by_order(k)->v); } } } } // namespace int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::setprecision(std::numeric_limits<Float>::max_digits10); Solve(); } #else // __INCLUDE_LEVEL__ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> template <class Key, class T, class Compare = std::less<>> using TreeMap = __gnu_pbds::tree<Key, T, Compare, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; template <class Key, class Compare = std::less<>> using TreeSet = TreeMap<Key, __gnu_pbds::null_type, Compare>; #define $(...) \ [&]<class T1 = int, class T2 = int>(T1&& $1 = 0, T2&& $2 = 0)->decltype(auto) { return __VA_ARGS__; } using Int = int64_t; using Float = double; namespace ranges = std::ranges; namespace views = std::views; inline constexpr auto Rev = views::reverse; inline constexpr auto Map = views::transform; inline constexpr auto Filter = views::filter; constexpr auto Rep(Int l, Int r) { return views::iota(std::min(l, r), r); } constexpr auto Rep(Int n) { return Rep(0, n); } constexpr auto Rep1(Int l, Int r) { return Rep(l, r + 1); } constexpr auto Rep1(Int n) { return Rep(1, n + 1); } constexpr Int Sz(auto&& r) { return static_cast<Int>(ranges::size(r)); } template <class T, class U = T> bool Chmin(T& x, U&& y) { return y < x && (x = std::forward<U>(y), true); } template <class T, class U = T> bool Chmax(T& x, U&& y) { return x < y && (x = std::forward<U>(y), true); } inline constexpr Int INF = [] { std::array<char, sizeof(Int)> a; a.fill(0x3f); return std::bit_cast<Int>(a); }(); template <class T> concept Range = ranges::range<T> && !std::convertible_to<T, std::string_view>; template <class T> concept TupleLike = std::__is_tuple_like<T>::value && !Range<T>; namespace std { istream& operator>>(istream& is, Range auto&& r) { for (auto&& e : r) { is >> e; } return is; } istream& operator>>(istream& is, TupleLike auto&& t) { return apply([&](auto&... xs) -> istream& { return (is >> ... >> xs); }, t); } ostream& operator<<(ostream& os, Range auto&& r) { for (string_view sep = ""; auto&& e : r) { os << exchange(sep, " ") << e; } return os; } ostream& operator<<(ostream& os, TupleLike auto&& t) { const auto f = [&](auto&... xs) -> ostream& { [[maybe_unused]] string_view sep = ""; ((os << exchange(sep, " ") << xs), ...); return os; }; return apply(f, t); } } // namespace std #define DEF_INC_OR_DEC(op) \ auto& operator op(Range auto&& r) { \ for (auto&& e : r) { \ op e; \ } \ return r; \ } \ auto& operator op(TupleLike auto&& t) { \ std::apply([](auto&... xs) { (op xs, ...); }, t); \ return t; \ } DEF_INC_OR_DEC(++) DEF_INC_OR_DEC(--) #undef DEF_INC_OR_DEC void Scan(auto&&... xs) { std::cin >> std::tie(xs...); } void Print(auto&&... xs) { std::cout << std::tie(xs...) << '\n'; } template <class F> class Fix { public: explicit Fix(F f) : f_(std::move(f)) {} decltype(auto) operator()(auto&&... xs) const { return f_(std::ref(*this), std::forward<decltype(xs)>(xs)...); } private: F f_; }; #endif // __INCLUDE_LEVEL__