結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #

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);
    }
}
0