Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.vk.vitalypavlenko.newSandbox.cartesian;
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.util.Random;
- import java.util.Scanner;
- public class CartesianTree2782 {
- private Node root;
- public CartesianTree2782() {
- }
- public void add(Integer newKey) {
- Node node = root;
- while (node != null && node.key != newKey) {
- if (newKey < node.key) {
- node = node.left;
- } else {
- node = node.right;
- }
- }
- if (node == null) {
- Node newNode = new Node(newKey);
- Pair<Node,Node> pair = split(root, newKey);
- root = merge(pair.first, merge(newNode, pair.second));
- }
- }
- Pair<Node,Node> split(Node node, Integer key) {
- if (node == null) {
- return new Pair<Node,Node>(null, null);
- }
- if (node.key < key) {
- Pair<Node,Node> pair = split(node.right, key);
- node.right = null;
- return new Pair<Node,Node>(merge(node, pair.first), pair.second);
- } else {
- Pair<Node,Node> pair = split(node.left, key);
- node.left = null;
- return new Pair<Node,Node>(pair.first, merge(pair.second, node));
- }
- }
- Node merge(Node left, Node right) {
- if (right == null) {
- return left;
- } else if (left == null) {
- return right;
- } else {
- if (left.height < right.height) {
- right.left = merge(left, right.left);
- return right;
- } else {
- left.right = merge(left.right, right);
- return left;
- }
- }
- }
- public Integer next(Integer key) {
- Pair<Node,Node> pair = split(root, key);
- Node node = pair.second;
- Integer res;
- if (node == null) {
- res = null;
- } else {
- while (node.left != null) {
- node = node.left;
- }
- res = node.key;
- }
- root = merge(pair.first, pair.second);
- return res;
- }
- static class Node {
- static Random generator = new Random(0);
- Integer key;
- int height;
- Node left, right;
- Node(int key) {
- this.key = key;
- this.height = generator.nextInt();
- }
- }
- public String toString() {
- StringBuffer sb = new StringBuffer();
- sb.append('{');
- printAscendingOrder(sb, root);
- if (sb.length() > 1) {
- sb.deleteCharAt(sb.length() - 1);
- }
- sb.append('}');
- return sb.toString();
- }
- private void printAscendingOrder(StringBuffer sb, Node node) {
- if (node == null) {
- return;
- }
- printAscendingOrder(sb, node.left);
- sb.append(node.key);
- sb.append(',');
- printAscendingOrder(sb, node.right);
- }
- public static void main(String[] args) {
- Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
- int n = in.nextInt();
- CartesianTree2782 ct = new CartesianTree2782();
- int lastResponse = 0;
- for (int i = 0; i < n; ++i) {
- String cmd = in.next("[\\+\\?]");
- int num = in.nextInt();
- if (cmd.equals("+")) {
- ct.add((num + lastResponse) % 1000000000);
- lastResponse = 0;
- } else {
- Integer res = ct.next(num);
- if (res == null) {
- System.out.println(lastResponse = -1);
- } else {
- System.out.println(lastResponse = res);
- }
- }
- }
- }
- }
- class Pair<A,B> {
- public A first;
- public B second;
- Pair(A first, B second) {
- this.first = first;
- this.second = second;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment