結果
問題 |
No.3298 K-th Slime
|
ユーザー |
![]() |
提出日時 | 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); } }