help to solve problem

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

help to solve problem

Post by Giorgi »

very interesting problem but I have no idea how to solve it.

input file contains several lines.
each line contains one or two integers.
if line contains one integer x then you should add x to your list;
if line contains two integers n and m then it is question: how many integers are between n an m in list? you should output answers to questions. number of questions less than 200000;
-1000000<=n,m<=1000000.

Code: Select all

input
2 3
5
2 6
5 6
7 8
9
3 9
5
3 9

output
0
1
1
0
2
2
help me please.
sorry for my english.
thankx;

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha »

With Binary search tree we can design a mechanism to achieve a solution with order O(nlogn)

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Post by Giorgi »

Moha wrote:With Binary search tree we can design a mechanism to achieve a solution with order O(nlogn)
please explain me more clearly, how can I do it?
I will insert the numbers in tree.
then I'll find successors until succesesor becomes more than right border. will it work?

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha »

No, Just save the total number of each subtrees in its root.
You may read the thread about problem 10909 in this forum.

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Post by Giorgi »

thank you :)

Post Reply

Return to “Algorithms”