結果
| 問題 |
No.3298 K-th Slime
|
| コンテスト | |
| ユーザー |
 InTheBloom
|
| 提出日時 | 2025-10-05 13:59:51 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 262 ms / 2,000 ms |
| コード長 | 9,848 bytes |
| コンパイル時間 | 2,298 ms |
| コンパイル使用メモリ | 204,532 KB |
| 実行使用メモリ | 25,912 KB |
| 最終ジャッジ日時 | 2025-10-05 14:00:06 |
| 合計ジャッジ時間 | 5,682 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 |
ソースコード
import std;
void main () {
int N, K, Q;
readln.read(N, K, Q);
auto A = readln.split.to!(int[]);
auto ans = new long[](0);
alias Tr = AVLTree!(long, true);
auto tree = new Tr();
foreach (i; 0 .. N) {
tree.insert(A[i]);
}
foreach (i; 0 .. Q) {
auto query = readln.split.to!(int[]);
int t = query[0];
if (t == 1) {
int x = query[1];
tree.insert(x);
}
if (t == 2) {
int y = query[1];
auto sp = tree.splitByLength(K);
long key = sp[0].back().value;
tree = Tr.merge(sp[0], sp[1]);
tree.remove(key);
tree.insert(key + y);
}
if (t == 3) {
auto sp = tree.splitByLength(K);
ans ~= sp[0].back().value;
tree = Tr.merge(sp[0], sp[1]);
}
}
writefln("%(%s\n%)", ans);
}
void read (T...) (string S, ref T args) {
import std.conv : to;
import std.array : split;
auto buf = S.split;
foreach (i, ref arg; args) {
arg = buf[i].to!(typeof(arg));
}
}
class AVLTree (T, bool allowDuplicate = false) {
alias TreeType = AVLTree!(T, allowDuplicate);
alias NodeType = TreeType.AVLNode;
struct AVLNode {
T value;
T acc;
int h;
int length;
AVLNode*[2] ch;
}
struct AVLSearchResult {
bool found;
T value;
}
this () {
root = null;
}
this (NodeType* node) {
root = node;
}
AVLNode* root;
static AVLNode* rotL (AVLNode* cur) {
assert(cur !is null && cur.ch[1] !is null);
auto rch = cur.ch[1];
cur.ch[1] = rch.ch[0];
rch.ch[0] = cur;
fix(cur);
fix(rch);
return rch;
}
static AVLNode* rotR (AVLNode* cur) {
assert(cur !is null && cur.ch[0] !is null);
auto lch = cur.ch[0];
cur.ch[0] = lch.ch[1];
lch.ch[1] = cur;
fix(cur);
fix(lch);
return lch;
}
// [AVLsubtree, 外されたノード]
static AVLNode*[2] removeLeftMost (AVLNode* cur) {
assert(cur !is null);
if (cur.ch[0] is null) {
return [cur.ch[1], cur];
}
auto ret = removeLeftMost(cur.ch[0]);
cur.ch[0] = ret[0];
return [balance(cur), ret[1]];
}
static void fix (AVLNode* cur) {
import std.algorithm: max;
assert(cur !is null);
int lh = 0;
int rh = 0;
T la = T.init;
T ra = T.init;
int ll = 0;
int rl = 0;
if (cur.ch[0] !is null) {
lh = cur.ch[0].h;
la = cur.ch[0].acc;
ll = cur.ch[0].length;
}
if (cur.ch[1] !is null) {
rh = cur.ch[1].h;
ra = cur.ch[1].acc;
rl = cur.ch[1].length;
}
cur.h = max(lh, rh) + 1;
cur.acc = la + cur.value + ra;
cur.length = ll + 1 + rl;
}
static int diff (AVLNode* cur) {
assert(cur !is null);
int lh = cur.ch[0] is null ? 0 : cur.ch[0].h;
int rh = cur.ch[1] is null ? 0 : cur.ch[1].h;
return lh - rh;
}
static AVLNode* balance (AVLNode* cur) {
import std.math: abs;
assert(cur !is null);
fix(cur);
int s = diff(cur);
assert(abs(s) <= 2);
if (abs(s) <= 1) {
return cur;
}
if (s == 2) {
if (diff(cur.ch[0]) == -1) {
cur.ch[0] = rotL(cur.ch[0]);
}
return rotR(cur);
}
if (diff(cur.ch[1]) == 1) {
cur.ch[1] = rotR(cur.ch[1]);
}
return rotL(cur);
}
static NodeType* mergeWithRoot (NodeType* lt, NodeType* r, NodeType* rt) {
assert(r !is null);
int ls = lt is null ? 0 : lt.h;
int rs = rt is null ? 0 : rt.h;
if (abs(ls - rs) <= 1) {
r.ch[0] = lt;
r.ch[1] = rt;
return balance(r);
}
if (ls < rs) {
rt.ch[0] = mergeWithRoot(lt, r, rt.ch[0]);
return balance(rt);
}
lt.ch[1] = mergeWithRoot(lt.ch[1], r, rt);
return balance(lt);
}
static TreeType merge (TreeType lt, TreeType rt) {
if (lt.empty()) {
return rt;
}
if (rt.empty()) {
return lt;
}
static if (allowDuplicate) {
enforce(lt.back().value <= rt.front().value);
}
else {
enforce(lt.back().value < rt.front().value);
}
auto rtt = removeLeftMost(rt.root);
return new TreeType(mergeWithRoot(lt.root, rtt[1], rtt[0]));
}
static NodeType*[2] internalSplitByValue (NodeType* node, T key) {
if (node is null) {
return [null, null];
}
if (node.value < key) {
auto sp = internalSplitByValue(node.ch[1], key);
auto lo = mergeWithRoot(node.ch[0], node, sp[0]);
return [lo, sp[1]];
}
auto sp = internalSplitByValue(node.ch[0], key);
auto hi = mergeWithRoot(sp[1], node, node.ch[1]);
return [sp[0], hi];
}
TreeType[2] splitByValue (T key) {
auto sp = internalSplitByValue(root, key);
return [new TreeType(sp[0]), new TreeType(sp[1])];
}
static NodeType*[2] internalSplitByLength (NodeType* node, size_t len) {
if (node is null) {
return [null, null];
}
int ll = (node.ch[0] is null ? 0 : node.ch[0].length);
if (ll + 1 <= len) {
auto sp = internalSplitByLength(node.ch[1], len - ll - 1);
auto lo = mergeWithRoot(node.ch[0], node, sp[0]);
return [lo, sp[1]];
}
auto sp = internalSplitByLength(node.ch[0], len);
auto hi = mergeWithRoot(sp[1], node, node.ch[1]);
return [sp[0], hi];
}
TreeType[2] splitByLength (size_t len) {
auto sp = internalSplitByLength(root, len);
return [new TreeType(sp[0]), new TreeType(sp[1])];
}
bool empty () {
return root is null;
}
AVLSearchResult front () {
auto cur = root;
if (cur is null) {
return AVLSearchResult(false);
}
while (cur.ch[0] !is null) {
cur = cur.ch[0];
}
return AVLSearchResult(true, cur.value);
}
AVLSearchResult back () {
auto cur = root;
if (cur is null) {
return AVLSearchResult(false);
}
while (cur.ch[1] !is null) {
cur = cur.ch[1];
}
return AVLSearchResult(true, cur.value);
}
bool find (T k) {
auto cur = root;
while (cur !is null) {
if (cur.value == k) {
return true;
}
cur = k < cur.value ? cur.ch[0] : cur.ch[1];
}
return false;
}
bool insert (T k) {
bool ret = true;
AVLNode* f (AVLNode* cur) {
if (cur is null) {
return new AVLNode(k, k, 1, 1);
}
static if (!allowDuplicate) {
if (cur.value == k) {
ret = false;
return cur;
}
}
int d = k < cur.value ? 0 : 1;
cur.ch[d] = f(cur.ch[d]);
return balance(cur);
}
root = f(root);
return ret;
}
bool remove (T k) {
bool del = true;
AVLNode* f (AVLNode* cur) {
if (cur is null) {
del = false;
return cur;
}
if (cur.value == k) {
if (cur.ch[1] is null) {
return cur.ch[0];
}
auto ret = removeLeftMost(cur.ch[1]);
ret[1].ch[0] = cur.ch[0];
ret[1].ch[1] = ret[0];
return balance(ret[1]);
}
int d = k < cur.value ? 0 : 1;
cur.ch[d] = f(cur.ch[d]);
return balance(cur);
}
root = f(root);
return del;
}
AVLSearchResult predecessor (T k) {
import std.algorithm: max;
AVLSearchResult f (AVLNode* cur) {
if (cur is null) {
return AVLSearchResult(false);
}
if (cur.value == k) {
return AVLSearchResult(true, cur.value);
}
if (cur.value < k) {
auto nex = f(cur.ch[1]);
if (!nex.found) {
return AVLSearchResult(true, cur.value);
}
nex.value = max(nex.value, cur.value);
return nex;
}
return f(cur.ch[0]);
}
return f(root);
}
AVLSearchResult successor (T k) {
import std.algorithm: min;
AVLSearchResult f (AVLNode* cur) {
if (cur is null) {
return AVLSearchResult(false);
}
if (cur.value == k) {
return AVLSearchResult(true, cur.value);
}
if (k < cur.value) {
auto nex = f(cur.ch[0]);
if (!nex.found) {
return AVLSearchResult(true, cur.value);
}
nex.value = min(nex.value, cur.value);
return nex;
}
return f(cur.ch[1]);
}
return f(root);
}
override string toString () {
import std.format;
auto values = new T[](0);
void f (AVLNode* cur) {
if (cur is null) {
return;
}
f(cur.ch[0]);
values ~= cur.value;
f(cur.ch[1]);
}
f(root);
return format("[%(%s, %)]", values);
}
}