Guest User

Cartesian tree for task #2782 on informatics.mccme.ru

a guest
Jan 25th, 2012
676
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.19 KB | None | 0 0
  1. package com.vk.vitalypavlenko.newSandbox.cartesian;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.InputStreamReader;
  5. import java.util.Random;
  6. import java.util.Scanner;
  7.  
  8. public class CartesianTree2782 {
  9.  
  10.     private Node root;
  11.    
  12.     public CartesianTree2782() {
  13.     }
  14.    
  15.     public void add(Integer newKey) {
  16.         Node node = root;
  17.         while (node != null && node.key != newKey) {
  18.             if (newKey < node.key) {
  19.                 node = node.left;
  20.             } else {
  21.                 node = node.right;
  22.             }
  23.         }
  24.         if (node == null) {
  25.             Node newNode = new Node(newKey);
  26.             Pair<Node,Node> pair = split(root, newKey);
  27.             root = merge(pair.first, merge(newNode, pair.second));
  28.         }
  29.     }
  30.    
  31.     Pair<Node,Node> split(Node node, Integer key) {
  32.         if (node == null) {
  33.             return new Pair<Node,Node>(null, null);
  34.         }
  35.         if (node.key < key) {
  36.             Pair<Node,Node> pair = split(node.right, key);
  37.             node.right = null;
  38.             return new Pair<Node,Node>(merge(node, pair.first), pair.second);
  39.         } else {
  40.             Pair<Node,Node> pair = split(node.left, key);
  41.             node.left = null;
  42.             return new Pair<Node,Node>(pair.first, merge(pair.second, node));
  43.         }
  44.     }
  45.    
  46.     Node merge(Node left, Node right) {
  47.         if (right == null) {
  48.             return left;
  49.         } else if (left == null) {
  50.             return right;
  51.         } else {
  52.             if (left.height < right.height) {
  53.                 right.left = merge(left, right.left);
  54.                 return right;
  55.             } else {
  56.                 left.right = merge(left.right, right);
  57.                 return left;
  58.             }
  59.         }
  60.     }
  61.    
  62.     public Integer next(Integer key) {
  63.         Pair<Node,Node> pair = split(root, key);
  64.         Node node = pair.second;
  65.         Integer res;
  66.         if (node == null) {
  67.             res = null;
  68.         } else {
  69.             while (node.left != null) {
  70.                 node = node.left;
  71.             }
  72.             res = node.key;
  73.         }
  74.         root = merge(pair.first, pair.second);
  75.         return res;
  76.     }
  77.    
  78.     static class Node {
  79.        
  80.         static Random generator = new Random(0);
  81.        
  82.         Integer key;
  83.         int height;
  84.        
  85.         Node left, right;
  86.        
  87.         Node(int key) {    
  88.             this.key = key;
  89.             this.height = generator.nextInt();
  90.         }
  91.        
  92.     }
  93.    
  94.     public String toString() {
  95.         StringBuffer sb = new StringBuffer();
  96.         sb.append('{');
  97.         printAscendingOrder(sb, root);
  98.         if (sb.length() > 1) {
  99.             sb.deleteCharAt(sb.length() - 1);
  100.         }
  101.         sb.append('}');
  102.         return sb.toString();
  103.     }
  104.    
  105.     private void printAscendingOrder(StringBuffer sb, Node node) {
  106.         if (node == null) {
  107.             return;
  108.         }
  109.         printAscendingOrder(sb, node.left);
  110.         sb.append(node.key);
  111.         sb.append(',');
  112.         printAscendingOrder(sb, node.right);
  113.     }
  114.    
  115.     public static void main(String[] args) {
  116.         Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
  117.         int n = in.nextInt();
  118.         CartesianTree2782 ct = new CartesianTree2782();
  119.         int lastResponse = 0;
  120.        
  121.         for (int i = 0; i < n; ++i) {
  122.             String cmd = in.next("[\\+\\?]");
  123.             int num = in.nextInt();
  124.            
  125.             if (cmd.equals("+")) {
  126.                 ct.add((num + lastResponse) % 1000000000);
  127.                 lastResponse = 0;
  128.             } else {
  129.                 Integer res = ct.next(num);
  130.                 if (res == null) {
  131.                     System.out.println(lastResponse = -1);
  132.                 } else {
  133.                     System.out.println(lastResponse = res);
  134.                 }
  135.             }
  136.         }
  137.     }
  138. }
  139.  
  140. class Pair<A,B> {
  141.    
  142.     public A first;
  143.     public B second;
  144.    
  145.     Pair(A first, B second) {
  146.         this.first = first;
  147.         this.second = second;
  148.     }
  149.    
  150. }
Advertisement
Add Comment
Please, Sign In to add comment