結果
| 問題 |
No.3298 K-th Slime
|
| ユーザー |
 coindarw
|
| 提出日時 | 2025-10-05 14:33:25 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 180 ms / 2,000 ms |
| コード長 | 18,616 bytes |
| コンパイル時間 | 5,423 ms |
| コンパイル使用メモリ | 334,524 KB |
| 実行使用メモリ | 11,520 KB |
| 最終ジャッジ日時 | 2025-10-05 14:33:40 |
| 合計ジャッジ時間 | 7,893 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using ll = long long;
using lll = __int128_t;
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n) - 1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define length(v) ((int)(v).size())
constexpr int inf = 2'000'000'000;
constexpr ll linf = 4'000'000'000'000'000'000, M7 = 1'000'000'007, M9 = 998'244'353;
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;
using namespace atcoder;
// clang-format off
using vint = vector<int>;using vvint = vector<vector<int>>;using vvvint = vector<vector<vector<int>>>;
using vll = vector<ll>;using vvll = vector<vector<ll>>;using vvvll = vector<vector<vector<ll>>>;
using vlll = vector<lll>;using vvlll = vector<vector<lll>>;using vvvlll = vector<vector<vector<lll>>>;
using vchar = vector<char>;using vvchar = vector<vector<char>>;using vvvchar = vector<vector<vector<char>>>;
using vstr = vector<string>;using vvstr = vector<vector<string>>;using vvvstr = vector<vector<vector<string>>>;
using vpi = vector<pair<int, int>>;using vvpi = vector<vector<pair<int, int>>>;using vvpint = vector<vector<pair<int, int>>>;
using vpl = vector<pair<ll, ll>>;using vvpl = vector<vector<pair<ll, ll>>>;using vvplint = vector<vector<pair<ll, int>>>;
using vbool = vector<bool>;using vvbool = vector<vector<bool>>;using vvvbool = vector<vector<vector<bool>>>;
#define Vec(type, ...) __make_vec<type>(__VA_ARGS__)
template <class T> vector<T> __make_vec(size_t a) {return vector<T>(a);}template <class T, class... Ts>
auto __make_vec(size_t a, Ts... ts) {return vector<decltype(__make_vec<T>(ts...))>(a, __make_vec<T>(ts...));}
#define VecI(init, type, ...) __make_vecI<type, init>(__VA_ARGS__)
template <class T, T init>vector<T> __make_vecI(size_t a) {return vector<T>(a, init);}
template <class T, T init, class... Ts>
auto __make_vecI(size_t a, Ts... ts) {return vector<decltype(__make_vecI<T, init>(ts...))>(a, __make_vecI<T, init>(ts...));}
template <typename T, typename U>inline ostream& operator<<(ostream& os, const pair<T, U>& p) noexcept {return os << p.first << " " << p.second;}
inline ostream& operator<<(ostream& os, const modint& m) noexcept { return os << m.val(); }
template <int M>inline ostream& operator<<(ostream& os, const static_modint<M>& m) noexcept { return os << m.val(); }
template <typename T> struct is_static_modint : std::false_type {}; template <int MOD> struct is_static_modint<static_modint<MOD>> : std::true_type {};
template <template <typename...> typename C, typename Number>concept MyContainer = std::is_same_v<C<Number>, std::vector<Number>> || std::is_same_v<C<Number>, std::deque<Number>> || std::is_same_v<C<Number>, std::set<Number>> || std::is_same_v<C<Number>, std::unordered_set<Number>> || std::is_same_v<C<Number>, std::unordered_multiset<Number>> || std::is_same_v<C<Number>, std::multiset<Number>>;
template <typename Number>concept MyNumber = std::is_same_v<Number, int> || std::is_same_v<Number, ll> || std::is_same_v<Number, char> || std::is_same_v<Number, modint> || is_static_modint<Number>::value;
template <template <typename...> typename C, typename Number>concept MyContainerNumber = MyContainer<C, Number> && MyNumber<Number>;
template <template <typename...> typename OutCon, template <typename...> typename InCon, typename Number>concept MyNestedContainerNumber = MyContainer<OutCon, InCon<Number>> && MyContainerNumber<InCon, Number>;
template <template <typename...> typename C, typename Number>requires MyContainerNumber<C, Number>std::ostream& operator<<(std::ostream& os, const C<Number>& t) {auto itr = t.begin();auto end = t.end();if (itr != end) {os << *itr++;for (; itr != end; ++itr) os << ' ' << *itr;}return os;}
template <template <typename...> typename OutCon, template <typename...> typename InCon, typename Number>requires MyNestedContainerNumber<OutCon, InCon, Number>std::ostream& operator<<(std::ostream& os, const OutCon<InCon<Number>>& t) {auto itr = t.begin();auto end = t.end();if (itr != end) {os << *itr++;for (; itr != end; ++itr) os << '\n' << *itr;}return os;}
template <typename T, typename U>istream& operator>>(istream& is, pair<T, U>& p) {return is >> p.first >> p.second;}
template <typename T>istream& operator>>(istream& is, vector<T>& v) {for (auto& e : v) is >> e;return is;}
void inp() {}
template <typename T, typename... Args>void inp(T& a, Args&... args) {cin >> a, inp(args...);}
template <typename T>void inp1(vector<T>& v, int offset = 1, int len = -1) {if (len == -1) len = int(v.size()) - offset;assert(offset >= 0 && len >= 0);for (int i = offset; i < offset + len; ++i) cin >> v[i];}
template <typename T>void oup(const T& a) {cout << a << "\n";}
template <typename T, typename... Args>void oup(const T& a, const Args&... args) {cout << a << " ", oup(args...);}
inline string YesNo(bool cond) { return cond ? "Yes" : "No"; }
inline auto add1(auto vec, ll offset = 1) {for (auto& e : vec) e += offset;return vec;}
#ifdef ONLINE_JUDGE
#define debug(...)
#else
#define debug(...) cerr << "<" << #__VA_ARGS__ << ">: ", debug_out(__VA_ARGS__)
template <typename T>void debug_out(T t) {cerr << t << "\n";}
template <typename T, typename... Args>void debug_out(T t, Args... args) {cerr << t << ", ";debug_out(args...);}
#endif
#ifdef ONLINE_JUDGE
#define todo(...) static_assert(false)
#else
#define todo(...)
#endif
// clang-format on
template <class S, S (*op)(S, S), S (*e)(), bool COMMUTATIVE, S (*reverse_prod)(S), bool LAZY, class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>
struct LazyLazyTreap {
static_assert((LAZY && !std::is_same_v<F, std::nullptr_t>) || (!LAZY && std::is_same_v<F, std::nullptr_t>), "F must be nullptr_t if LAZY is false");
private:
template <typename U, typename = void>
struct has_fail_member : std::false_type {};
template <typename U>
struct has_fail_member<U, std::void_t<decltype(std::declval<U>().fail)>> : std::true_type {};
static constexpr bool beats = has_fail_member<S>::value;
static_assert(!beats || LAZY, "beats! requires LAZY");
template <class FF, nullptr_t Dummy = nullptr>
struct _Node {
_Node *l, *r;
uint32_t pri;
int size;
bool rev;
S val, prod;
FF lazy;
bool is_id;
};
template <nullptr_t Dummy>
struct _Node<void, Dummy> {
_Node *l, *r;
uint32_t pri;
int size;
bool rev;
S val, prod;
};
using Node = std::conditional_t<LAZY, _Node<F>, _Node<void>>;
static Node* _alloc(Node* t = nullptr) {
static std::deque<Node> pool;
static std::vector<Node*> pool_used;
if (t != nullptr) {
pool_used.emplace_back(t);
return t;
}
if (pool_used.empty()) {
pool.emplace_back();
return &pool.back();
}
Node* ptr = pool_used.back();
pool_used.pop_back();
return ptr;
}
static void _delete_node(Node* t) { _alloc(t); }
Node* _new_node(S val) {
Node* ptr = _alloc();
static mt19937 mt(std::random_device{}());
if constexpr (LAZY) {
*ptr = {nullptr, nullptr, uint32_t(mt()), 1, false, val, val, id(), true};
} else {
*ptr = {nullptr, nullptr, uint32_t(mt()), 1, false, val, val};
}
return ptr;
}
int _size(Node* t) const { return t != nullptr ? t->size : 0; }
void _all_apply(Node* t, F f) {
if (t == nullptr) return;
t->val = mapping(f, t->val);
t->prod = mapping(f, t->prod);
t->lazy = composition(f, t->lazy);
t->is_id = false;
if (t->l || t->r) {
if constexpr (beats) {
if (t->prod.fail) _push(t), _update(t);
}
}
}
void _push(Node* t) {
if (t == nullptr) return;
if constexpr (LAZY) {
if (!t->is_id) {
if (t->l != nullptr) _all_apply(t->l, t->lazy);
if (t->r != nullptr) _all_apply(t->r, t->lazy);
t->lazy = id();
t->is_id = true;
}
}
if (t->rev) {
std::swap(t->l, t->r);
if (t->l != nullptr) {
t->l->rev ^= 1;
if constexpr (!COMMUTATIVE) t->l->val = reverse_prod(t->l->val);
}
if (t->r != nullptr) {
t->r->rev ^= 1;
if constexpr (!COMMUTATIVE) t->r->val = reverse_prod(t->r->val);
}
t->rev = false;
}
}
void _update(Node* t) {
t->size = _size(t->l) + _size(t->r) + 1;
t->prod = t->val;
if (t->l != nullptr) t->prod = op(t->l->prod, t->prod);
if (t->r != nullptr) t->prod = op(t->prod, t->r->prod);
}
Node* _merge(Node* l, Node* r) {
if (l == nullptr) return r;
if (r == nullptr) return l;
if (l->pri > r->pri) {
_push(l);
l->r = _merge(l->r, r);
_update(l);
return l;
} else {
_push(r);
r->l = _merge(l, r->l);
_update(r);
return r;
}
}
pair<Node*, Node*> _split(Node* t, int k) {
if (t == nullptr) return {nullptr, nullptr};
if (k == 0) return {nullptr, t};
if (k == _size(t)) return {t, nullptr};
_push(t);
if (k <= _size(t->l)) {
auto [l, r] = _split(t->l, k);
t->l = r;
_update(t);
return {l, t};
} else {
auto [l, r] = _split(t->r, k - _size(t->l) - 1);
t->r = l;
_update(t);
return {t, r};
}
}
Node* _insert(Node* t, int k, S val) {
auto x = _split(t, k);
return _merge(_merge(x.first, _new_node(val)), x.second);
}
Node* _erase(Node* t, int k) {
auto x = _split(t, k);
auto y = _split(x.second, 1);
_delete_node(y.first);
return _merge(x.first, y.second);
}
Node* _apply(Node* t, const F& f, int l, int r) {
auto [a, b] = _split(t, l);
auto [c, d] = _split(b, r - l);
_all_apply(c, f);
return _merge(a, _merge(c, d));
}
S _prod(Node*& t, int l, int r) {
auto [a, b] = _split(t, l);
auto [c, d] = _split(b, r - l);
_push(c);
S res = c->prod;
t = _merge(a, _merge(c, d));
return res;
}
Node* _reverse(Node* t, int l, int r) {
auto [a, b] = _split(t, l);
auto [c, d] = _split(b, r - l);
c->rev ^= 1;
if constexpr (!COMMUTATIVE) c->val = reverse_prod(c->val);
return _merge(_merge(a, c), d);
}
Node* _build(int l, int r, const std::vector<S>& v) {
if (l + 1 >= r) return _new_node(v[l]);
int mid = (l + r) / 2;
return _merge(_build(l, mid, v), _build(mid, r, v));
}
void _set(Node* t, int k, const S& val) {
if (t == nullptr) return;
_push(t);
if (k < _size(t->l)) {
_set(t->l, k, val);
} else if (k == _size(t->l)) {
t->val = val;
} else {
_set(t->r, k - _size(t->l) - 1, val);
}
_update(t);
}
S _get(Node* t, int k) {
if (t == nullptr) return e();
_push(t);
if (k < _size(t->l)) {
return _get(t->l, k);
} else if (k == _size(t->l)) {
return t->val;
} else {
return _get(t->r, k - _size(t->l) - 1);
}
}
std::string _to_string(Node* t) {
std::stringstream ss;
int cnt = _size(t);
std::function<void(Node*)> dfs = [&](Node* t) {
if (t == nullptr) return;
_push(t);
dfs(t->l);
ss << t->val;
if (--cnt) ss << " ";
dfs(t->r);
};
dfs(t);
return ss.str();
}
pair<S, int> _max_right_sub(Node* p, int nl, int nr, S left, function<bool(S)> f) {
_push(p);
S nxt = op(left, p->prod);
if (f(nxt)) {
return {nxt, nr};
} else if (p->l == nullptr && p->r == nullptr) {
return {left, nl};
}
int lsz = _size(p->l);
if (p->l) {
auto [left_res, left_idx] = _max_right_sub(p->l, nl, nl + lsz, left, f);
if (left_idx != nl + lsz) return {left_res, left_idx};
left = left_res;
}
S nxtt = op(left, p->val);
if (!f(nxtt)) return {left, nl + lsz};
if (p->r) return _max_right_sub(p->r, nl + lsz + 1, nr, nxtt, f);
assert(false);
}
pair<S, int> _min_left_sub(Node* p, int nl, int nr, S right, function<bool(S)> f) {
_push(p);
S nxt = op(p->prod, right);
if (f(nxt)) {
return {nxt, nl};
} else if (p->l == nullptr && p->r == nullptr) {
return {right, nr};
}
int rsz = _size(p->r);
if (p->r) {
auto [right_res, right_idx] = _min_left_sub(p->r, nr - rsz, nr, right, f);
if (right_idx != nr - rsz) return {right_res, right_idx};
right = right_res;
}
S nxtt = op(p->val, right);
if (!f(nxtt)) return {right, nr - rsz};
if (p->l) return _min_left_sub(p->l, nl, nr - rsz - 1, nxtt, f);
assert(false);
}
Node* root;
LazyLazyTreap(Node* t) : root(t) {}
public:
LazyLazyTreap() : root(nullptr) {}
LazyLazyTreap(const std::vector<S>& v) : root(_build(0, v.size(), v)) {}
LazyLazyTreap(const LazyLazyTreap& t) : root(t.root) {
std::vector<S> v;
auto dfs = [&](auto dfs, Node* t) -> void {
if (t == nullptr) return;
_push(t);
dfs(dfs, t->l);
v.push_back(t->val);
dfs(dfs, t->r);
};
dfs(dfs, root);
root = _build(0, v.size(), v);
}
LazyLazyTreap(LazyLazyTreap&& t) : root(t.root) { t.root = nullptr; }
void merge(LazyLazyTreap& t) { root = _merge(root, t.root); }
std::pair<LazyLazyTreap, LazyLazyTreap> split(int k) {
auto [l, r] = _split(root, k);
root = nullptr;
return {LazyLazyTreap(l), LazyLazyTreap(r)};
}
void insert(int k, S val) {
assert(0 <= k && k <= _size(root));
root = _insert(root, k, val);
}
void erase(int k) {
assert(0 <= k && k < _size(root));
root = _erase(root, k);
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _size(root));
if (l == r) return e();
return _prod(root, l, r);
}
void apply(int l, int r, const F& f) {
assert(0 <= l && l <= r && r <= _size(root));
static_assert(LAZY);
if (l == r) return;
root = _apply(root, f, l, r);
}
void reverse(int l, int r) {
assert(0 <= l && l <= r && r <= _size(root));
if (l == r) return;
root = _reverse(root, l, r);
}
void set(int k, S val) {
assert(0 <= k && k < _size(root));
_set(root, k, val);
}
S get(int k) {
assert(0 <= k && k < _size(root));
return _get(root, k);
}
int size() const { return _size(root); }
bool empty() const { return root == nullptr; }
friend std::ostream& operator<<(std::ostream& os, LazyLazyTreap& tr) {
os << tr._to_string(tr.root);
return os;
}
void push_back(S val) { root = _merge(root, _new_node(val)); }
void pop_back() {
assert(_size(root));
root = _erase(root, _size(root) - 1);
}
void push_front(S val) { root = _merge(_new_node(val), root); }
void pop_front() {
assert(_size(root));
root = _erase(root, 0);
}
int max_right(int l, function<bool(S)> f) {
int n = _size(root);
assert(0 <= l && l <= n);
assert(f(e()));
if (l == n) return n;
auto [x, y] = _split(root, l);
int res = _max_right_sub(y, 0, n - l, e(), f).second + l;
root = _merge(x, y);
return res;
}
int min_left(int r, function<bool(S)> f) {
int n = _size(root);
assert(0 <= r && r <= n);
assert(f(e()));
if (r == 0) return 0;
auto [x, y] = _split(root, r);
int res = _min_left_sub(x, 0, r, e(), f).second;
root = _merge(x, y);
return res;
}
bool is_beats() const { return beats; }
LazyLazyTreap& operator+(LazyLazyTreap& t) {
merge(t);
return *this;
}
LazyLazyTreap& operator=(LazyLazyTreap& t) {
root = t.root;
t.root = nullptr;
return *this;
}
};
template <typename S>
static S dummy_reverse_prod(S s) {
return s;
}
template <typename S>
static S dummy_mapping(nullptr_t f, S s) {
return s;
}
static nullptr_t dummy_composition(nullptr_t f, nullptr_t g) { return f; }
static nullptr_t dummy_id() { return nullptr; }
template <class S, S (*op)(S, S), S (*e)(), bool COMMUTATIVE = true, S (*reverse_prod)(S) = dummy_reverse_prod>
using Treap = LazyLazyTreap<S, op, e, COMMUTATIVE, reverse_prod, false, nullptr_t, dummy_mapping, dummy_composition, dummy_id>;
template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)(), bool COMMUTATIVE = true, S (*reverse_prod)(S) = dummy_reverse_prod>
using LazyTreap = LazyLazyTreap<S, op, e, COMMUTATIVE, reverse_prod, true, F, mapping, composition, id>;
ll op(ll x, ll y) { return max(x, y); }
ll e() { return -linf; }
#pragma GCC diagnostic push
#pragma GCC diagnostic error "-Wshadow"
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, k, q;
inp(n, k, q);
vll a(n);
inp(a);
sort(all(a));
Treap<ll, op, e> tr;
rep(i, n) tr.push_back(a[i]);
auto insert = [&](ll x) -> void {
int idx = tr.max_right(0, [&](auto y) { return x >= y; });
// debug(x, idx);
debug(idx, x, tr);
tr.insert(idx, x);
};
rep(i, q) {
ll c;
inp(c);
debug(tr);
if (c == 1) {
ll x;
inp(x);
insert(x);
} else if (c == 2) {
ll y;
inp(y);
ll z = tr.get(k - 1);
tr.erase(k - 1);
insert(z + y);
} else {
oup(tr.get(k - 1));
}
}
}
#pragma GCC diagnostic pop