fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. class Main{
  5.     public static void main(String args[]) throws Exception{
  6.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  7.         int N = Integer.parseInt(br.readLine());
  8.         AVLTree tree = new AVLTree();
  9.         for(int i=0; i<N; i++){
  10.             int m = Integer.parseInt(br.readLine());
  11.             tree.insert(m);
  12.             int r = tree.greaterThan(m)+1;
  13.             System.out.println(r);
  14.         }
  15.     }
  16. }
  17.  
  18. class AVLTree{
  19.     static class Node{
  20.         int key, height, size;
  21.         Node left, right;
  22.  
  23.         Node(int k){
  24.             key = k;
  25.             height = size = 1;
  26.         }
  27.  
  28.         void update(){
  29.             height = Math.max(getHeight(left), getHeight(right)) + 1;
  30.             size = getSize(left) + getSize(right) + 1;
  31.         }
  32.  
  33.         static int getHeight(Node n){
  34.             return n==null?0:n.height;
  35.         }
  36.  
  37.         static int getSize(Node n){
  38.             return n==null?0:n.size;
  39.         }
  40.     }
  41.  
  42.     Node root;
  43.  
  44.     Node rotateRight(Node p){
  45.         Node c = p.left;
  46.         Node g = c.right;
  47.         p.left = g;
  48.         c.right = p;
  49.         p.update();
  50.         c.update();
  51.  
  52.         return c;
  53.     }
  54.  
  55.     Node rotateLeft(Node p){
  56.         Node c = p.right;
  57.         Node g = c.left;
  58.         p.right = g;
  59.         c.left = p;
  60.         p.update();
  61.         c.update();
  62.  
  63.         return c;
  64.     }
  65.  
  66.     Node insert(Node n, int key){
  67.  
  68.         if(n==null)
  69.             return new Node(key);
  70.  
  71.         if(key<n.key)
  72.             n.left = insert(n.left, key);
  73.         else if(key>n.key)
  74.             n.right = insert(n.right, key);
  75.         else
  76.             return n;
  77.         n.update();
  78.  
  79.         int bal = Node.getHeight(n.left) - Node.getHeight(n.right);
  80.  
  81.         if(bal>1 && key<n.left.key)
  82.             return rotateRight(n);
  83.         if(bal<-1 && key>n.right.key)
  84.             return rotateLeft(n);
  85.         if(bal>1 && key>n.left.key){
  86.             n.left = rotateLeft(n.left);
  87.             return rotateRight(n);
  88.         }
  89.         if(bal<-1 && key<n.right.key){
  90.             n.right = rotateRight(n.right);
  91.             return rotateLeft(n);
  92.         }
  93.  
  94.         return n;
  95.     }
  96.  
  97.     void insert(int key){
  98.         root = insert(root, key);
  99.     }
  100.  
  101.     int greaterThan(int key){
  102.         Node n = root;
  103.         int count = 0;
  104.         while(n!=null){
  105.             if(key<n.key){
  106.                 count += 1 + Node.getSize(n.right);
  107.                 n = n.left;
  108.             }
  109.             else if(key==n.key){
  110.                 count += Node.getSize(n.right);
  111.                 break;
  112.             }
  113.             else
  114.                 n = n.right;
  115.         }
  116.         return count;
  117.     }
  118. }
Success #stdin #stdout 0.04s 711168KB
comments (?)
stdin
copy 
6
78
24
68
40
39
89
stdout
copy 
1
2
2
3
4
1
https://ideone.com/vw82rv
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!