SHARE
TWEET

Untitled

a guest Apr 20th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.Scanner;
  3.  
  4. public class Main {
  5.     static Node root;
  6.     static int currentValue = 0;
  7.     static int size = 0;
  8.     public static void main(String[] args) throws IOException {
  9.         InputStreamReader reader = new InputStreamReader(System.in);
  10.         BufferedReader in = new BufferedReader(reader);
  11.         OutputStream out = new BufferedOutputStream(System.out);
  12.         String line = in.readLine();
  13.         while (in.ready()) {
  14.             line = in.readLine();
  15.             String[] keyWords = line.split(" ");
  16.             long value = Long.parseLong(keyWords[1]);
  17.             switch(keyWords[0]) {
  18.                 case "+1":
  19.                     insert(value);
  20.                    // update(root);
  21.                     break;
  22.                 case "1":
  23.                     insert(value);
  24.                     break;
  25.                 case "0":
  26.                     Node current = root;
  27.                     out.write(Integer.toString((int)findNumberMax(root, size - value + 1)).getBytes());
  28.                     out.flush();
  29.                     break;
  30.                 case "-1":
  31.                     delete(value);
  32.                     break;
  33.             }
  34.             Node current = root;
  35.         }
  36.         in.close();
  37.         out.close();
  38.     }
  39.  
  40.     public static class Node {
  41.         long dataFirst;
  42.         long dataSecond;
  43.         long sum = 0;
  44.         Node left = null;
  45.         Node right = null;
  46.         Node parent = null;
  47.         public Node (long dataFirst, long dataSecond, Node parent) {
  48.             this.dataFirst = dataFirst;
  49.             this.dataSecond = dataSecond;
  50.             this.parent = parent;
  51.         }
  52.         public Node (long dataFirst, Node parent) {
  53.             this.dataFirst = dataFirst;
  54.             this.dataSecond = currentValue;
  55.             currentValue++;
  56.             this.parent = parent;
  57.         }
  58.     }
  59.     public static Pair split(Node root, long value) {
  60.         Pair pair;
  61.         if (root == null) {
  62.             return new Pair(null, null);
  63.         } else {
  64.             if (root.dataFirst < value) {
  65.                 pair = split(root.right, value);
  66.                 root.right = pair.first;
  67.                 pair.first = root;
  68.             } else {
  69.                 pair = split(root.left, value);
  70.                 root.left = pair.second;
  71.                 pair.second = root;
  72.             }
  73.         }
  74.         update(pair.first);
  75.         update(pair.second);
  76.         return pair;
  77.     }
  78.     public static Node merge(Node first, Node second) {
  79.         if (first == null || second == null) {
  80.             return first == null ? second : first;
  81.         } else {
  82.             if (first.dataSecond > second.dataSecond) {
  83.                 first.right = merge(first.right, second);
  84.                 update(first);
  85.                 return first;
  86.             } else {
  87.                 second.left = merge(first, second.left);
  88.                 update(second);
  89.                 return second;
  90.             }
  91.         }
  92.     }
  93.     public static void update(Node root) {
  94.         if (root == null) {
  95.             return;
  96.         } else {
  97.             root.dataSecond = 1 + getSum(root.left) + getSum(root.right);
  98.         }
  99.     }
  100.     public static long getSum(Node current) {
  101.         if (current == null) {
  102.             return 0;
  103.         } else {
  104.             return current.dataSecond;
  105.         }
  106.     }
  107.     public static class Pair {
  108.         Node first;
  109.         Node second;
  110.         public Pair(Node first, Node second) {
  111.             this.first = first;
  112.             this.second = second;
  113.         }
  114.     }
  115.     public static void insert(long data) {
  116.         Node forInsert = new Node(data, null);
  117.         if (exists(forInsert.dataFirst)) {
  118.             return;
  119.         } else {
  120.             Pair pair;
  121.             pair = split(root, data);
  122.             pair.first = merge(pair.first, forInsert);
  123.             root = merge(pair.first, pair.second);
  124.             size++;
  125.         }
  126.     }
  127.     public static boolean exists(long data) {
  128.         boolean contains = false;
  129.         Pair pair = split(root, data);
  130.         Pair secondPair = split(pair.second, data + 1);
  131.         if (secondPair.first != null) {
  132.             contains = true;
  133.         }
  134.         Node kek = merge(pair.first, secondPair.first);
  135.         root = merge(kek, secondPair.second);
  136.         return contains;
  137.     }
  138.     public static long sum(long dataFirst, long dataSecond) {
  139.         Pair first, second;
  140.         first = split(root, dataFirst);
  141.         second = split(first.second, dataSecond + 1);
  142.         long answer = getSum(second.first);
  143.         Node current = merge(second.first, second.second);
  144.         root = merge(first.first, current);
  145.         return answer;
  146.     }
  147.  
  148.     public static void delete(long data) {
  149.         Pair first, second;
  150.         first = split(root, data);
  151.         second = split(first.second, data + 1);
  152.         root = merge(first.first, second.second);
  153.         size--;
  154.     }
  155.  
  156.     public static void next(long data) {
  157.         Pair pair = split(root, data + 1);
  158.         Node current = pair.second;
  159.         if (current == null) {
  160.             System.out.println("none");
  161.             return;
  162.         }
  163.         while (current.left != null) {
  164.             current = current.left;
  165.         }
  166.         root = merge(pair.first, pair.second);
  167.         System.out.println(current.dataFirst);
  168.     }
  169.  
  170.     public static void prev(long data) {
  171.         Pair pair = split(root, data);
  172.         Node current = pair.first;
  173.         if (current == null) {
  174.             System.out.println("none");
  175.             return;
  176.         }
  177.         while (current.right != null) {
  178.             current = current.right;
  179.         }
  180.         root = merge(pair.first, pair.second);
  181.         System.out.println(current.dataFirst);
  182.     }
  183.  
  184.     public static long findNumberMax(Node root, long data) {
  185.         long currentNumber = 1;
  186.         try {
  187.             if (root.left != null) {
  188.                 currentNumber += root.left.dataSecond;
  189.             }
  190.             if (currentNumber == data) {
  191.                 return root.dataFirst;
  192.             } else if (currentNumber < data) {
  193.                 return findNumberMax(root.right, data - currentNumber);
  194.             } else {
  195.                 return findNumberMax(root.left, data);
  196.             }
  197.         } catch (NullPointerException e) {
  198.             return root.dataFirst;
  199.         }
  200.     }
  201.  
  202.     public static void inOrderTraversal(Node root) {
  203.         if (root != null) {
  204.             inOrderTraversal(root.left);
  205.             System.out.println(root.dataFirst + " " + root.dataSecond);
  206.             inOrderTraversal(root.right);
  207.         }
  208.     }
  209. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top