結果
| 問題 |
No.3298 K-th Slime
|
| コンテスト | |
| ユーザー |
 EvbCFfp1XB
|
| 提出日時 | 2025-10-05 15:59:33 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,320 ms / 2,000 ms |
| コード長 | 8,428 bytes |
| コンパイル時間 | 3,366 ms |
| コンパイル使用メモリ | 90,456 KB |
| 実行使用メモリ | 68,852 KB |
| 最終ジャッジ日時 | 2025-10-05 15:59:54 |
| 合計ジャッジ時間 | 20,085 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 25 |
ソースコード
import java.util.Comparator;
import java.util.Random;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
try (Scanner in = new Scanner(System.in)) {
int n = in.nextInt();
int k = in.nextInt() - 1;
int q = in.nextInt();
MyTreap<Long> tree = new MyTreap<Long>((o1, o2) -> Long.compare(o1.longValue(), o2.longValue()));
for (int i = 0; i < n; i++) {
tree.add(in.nextLong());
}
for (int _q = 0; _q < q; _q++) {
int m = in.nextInt();
if (m == 1) {
long x = in.nextLong();
tree.add(x);
} else if (m == 2) {
long y = in.nextLong();
long removed = tree.remove(k).longValue();
tree.add(removed + y);
} else if (m == 3) {
System.out.println(tree.get(k));
}
}
}
}
}
class MyTreap<T> {
private class Node<S> {
private Node<S> l;
private Node<S> r;
private int priority;
private T value;
private int size;
public Node(T value) {
super();
this.priority = rand.nextInt();
this.value = value;
this.size = 1;
}
}
private static final Random rand = new Random(System.nanoTime());
private Comparator<T> comparator;
private Node<T> root;
public MyTreap(Comparator<T> comparator) {
this.comparator = comparator;
}
public T get(int index) {
return get(root, index);
}
private T get(Node<T> node, int index) {
if (node == null) {
return null;
}
int sizeNodeL = sz(node.l);
if (index == sizeNodeL) {
return node.value;
} else if (index < sizeNodeL) {
return get(node.l, index);
} else {
return get(node.r, index - 1 - sizeNodeL);
}
}
public void add(T value) {
root = add(root, new Node<T>(value));
}
private Node<T> add(Node<T> node, Node<T> add) {
if (node == null) {
return add;
}
int compare = comparator.compare(add.value, node.value);
if (compare <= 0) {
node.l = add(node.l, add);
} else {
node.r = add(node.r, add);
}
node.size++;
if (compare <= 0) {
if (node.l.priority < node.priority) {
node = rotateR(node);
}
} else {
if (node.r.priority < node.priority) {
node = rotateL(node);
}
}
return node;
}
public void remove(T value) {
root = remove(root, value);
}
private Node<T> remove(Node<T> node, T value) {
if (node == null) {
return null;
}
int compare = comparator.compare(value, node.value);
if (compare == 0) {
node = remove(node);
if (node == null) {
return node;
}
} else if (compare < 0) {
node.l = remove(node.l, value);
} else {
node.r = remove(node.r, value);
}
node.size = size(node);
return node;
}
private Node<T> remove(Node<T> node) {
if (node.l == null && node.r == null) {
clear(node);
return null;
}
Node<T> rotate;
if (node.r == null || (node.l != null && node.l.priority <= node.r.priority)) {
rotate = rotateR(node);
rotate.r = remove(node);
} else {
rotate = rotateL(node);
rotate.l = remove(node);
}
rotate.size--;
return rotate;
}
public T remove(int index) {
T value = get(index);
remove(value);
return value;
}
public boolean contains(T value) {
return contains(root, value);
}
private boolean contains(Node<T> node, T value) {
if (node == null) {
return false;
}
int compare = comparator.compare(value, node.value);
if (compare == 0) {
return true;
} else if (compare < 0) {
return contains(node.l, value);
} else {
return contains(node.r, value);
}
}
public int indexOf(T value) {
return indexOf(root, value, 0);
}
private int indexOf(Node<T> node, T value, int index) {
if (node == null) {
return -1;
}
int compare = comparator.compare(value, node.value);
if (compare == 0) {
int indexL = indexOf(node.l, value, index);
return indexL != -1 ? indexL : (index + sz(node.l));
} else if (compare < 0) {
return indexOf(node.l, value, index);
} else {
return indexOf(node.r, value, index + 1 + sz(node.l));
}
}
public int indexOfIfExists(T value) {
return indexOfIfExists(root, value, 0);
}
private int indexOfIfExists(Node<T> node, T value, int index) {
if (node == null) {
return index;
}
int compare = comparator.compare(value, node.value);
// if (compare == 0) {
// int indexL = indexOfIfExists(node.l, value, index);
// return indexL != -1 ? indexL : (index + sz(node.l));
// } else
if (compare <= 0) {
return indexOfIfExists(node.l, value, index);
} else {
return indexOfIfExists(node.r, value, index + 1 + sz(node.l));
}
}
public int lastIndexOf(T value) {
return lastIndexOf(root, value, 0);
}
private int lastIndexOf(Node<T> node, T value, int index) {
if (node == null) {
return -1;
}
int compare = comparator.compare(value, node.value);
if (compare == 0) {
int indexR = lastIndexOf(node.r, value, index + 1 + sz(node.l));
return indexR != -1 ? indexR : (index + sz(node.l));
} else if (compare < 0) {
return lastIndexOf(node.l, value, index);
} else {
return lastIndexOf(node.r, value, index + 1 + sz(node.l));
}
}
public int lastIndexOfIfExists(T value) {
return lastIndexOfIfExists(root, value, 0);
}
private int lastIndexOfIfExists(Node<T> node, T value, int index) {
if (node == null) {
return index;
}
int compare = comparator.compare(value, node.value);
// if (compare == 0) {
// int indexR = lastIndexOfIfExists(node.r, value, index + 1 + sz(node.l));
// return indexR != -1 ? indexR : (index + sz(node.l));
// } else
if (compare < 0) {
return lastIndexOfIfExists(node.l, value, index);
} else {
return lastIndexOfIfExists(node.r, value, index + 1 + sz(node.l));
}
}
private Node<T> rotateR(Node<T> node) {
Node<T> l = node.l;
Node<T> lr = l.r;
node.l = lr;
l.r = node;
node.size = size(node);
l.size = size(l);
return l;
}
private Node<T> rotateL(Node<T> node) {
Node<T> r = node.r;
Node<T> rl = r.l;
node.r = rl;
r.l = node;
node.size = size(node);
r.size = size(r);
return r;
}
private int size(Node<T> node) {
if (node == null) {
return 0;
}
return 1 + sz(node.l) + sz(node.r);
}
public int size() {
return sz(root);
}
private int sz(Node<T> node) {
return node == null ? 0 : node.size;
}
public boolean isEmpty() {
return size() <= 0;
}
private void clear(Node<T> node) {
node.value = null;
node.l = null;
node.r = null;
node = null;
}
public void print() {
print(root, 0);
System.err.println();
}
private void print(Node<T> node, int depth) {
if (node == null) {
return;
}
print(node.l, depth + 1);
for (int i = 0; i < depth; i++) {
System.err.print(" ");
}
System.err.println(node.value + " " + node.size + " " + node.priority);
print(node.r, depth + 1);
}
}