COCI 2008/2009, Contest #3

Task BST

A binary search tree is a tree in which every node has at most two child nodes (a left and a right child). Each node had an integer written insude it. If the number X is written inside a node, then the numbers in its left subtree are less than X and the numbers in its right subtree are greater than X.

You will be given a sequence of integers between 1 and N such that each number appears in the sequence exactly once. You are to create a binary search tree from the sequence, putting the first number in the root node and inserting every other number in order. In other words, run insert( X, root ) for every other number:

insert( number X, node N )
   increase the counter C by 1
   if X is less than the number in node N
      if N has no left child
         create a new node with the number X and set it to be the left child of node N
      else
         insert( X, left child of node N )
   else (X is greater than the number in node N)
      if N has no right child
         create a new node with the number X and set it to be the right child of node N
      else
         insert( X, right child of node N )

Write a program that calculates the value of C after every number is inserted. You may assume the counter is initially 0.

Input

The first line contains the integer N (1 ≤ N ≤ 300 000), the length of the sequence.

The remaining N lines contain the numbers in the sequence, integers in the interval [1..N]. The numbers will be distinct.

Output

Output N integers each on its own line, the values of the counter C after each number is inserted into the tree.

Scoring

In test cases worth 50% of points, N will be at most 1000.

Examples

4
1
2
3
4

0
1
3
6

5
3
2
4
1
5

0
1
2
4
6

8
3
5
1
6
8
7
2
4

0
1
2
4
7
11
13
15

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 32M
Added: Dec 13, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Hi :) I have implemented best algorithm in my knowledge but I was only able to clear few test cases :( .I tried with fast io but that too timed out.I changed new to malloc but that was also TLE.Please check admin :)

Sorry, you do not have the correct algorithm. Directly implementing a BST is not fast enough. (Incidentally, malloc is not faster than new, especially for POD types.)

In general, if the problem has more than about 20 accepted users, the problem itself is probably fine.

Hi :) I was not claiming that problem is wrong it must be correct.My point was just asking for help since I don't know anything better than this :) .Would you mind giving me any hint :) Thanks a lot for your reply though :) :)

So this is a hint, your program runs at a time complexity of O(n^2), which is too slow, remember a binary search tree searches in log(n) time, and you want your program to run O(n log(n)) speed, which means you need to think about what your are doing when inserting and querying, and you can simplify to search N times to get the run time complexity of O(n log(n))

The first number is automatically put as the root, and nothing happens to the counter.
All the other numbers are inserted normally, though.