please give me some hints how to solve the problem fast i.e.
O(n*ln(n)) or O(n*sqrt(n)).

Create Sqrt(N) buckets:
In bucket k store amount of start in such range:
[(k-1)*Sqrt(32000);  k*Sqrt(32000))
When placing a star find bucket were it is situated O(Sqrt(N))
Add all buckets wich are lefter O(Sqrt(N))
In current bucket range check all stars. O(1) Because Sqrt(32000)=O(1)
Update bucket! O(1)

I used next:
b[i] - number of start with x <= i.

P.S. Bucket may be any size. For speed I chose bucket size 128. So I
fastly can find bucket num: x shr 7.

If something explained badly, ask.

Good luck!

> Create Sqrt(N) buckets:
> In bucket k store amount of start in such range:
> [(k-1)*Sqrt(32000);  k*Sqrt(32000))
> When placing a star find bucket were it is situated O(Sqrt(N))
> Add all buckets wich are lefter O(Sqrt(N))
> In current bucket range check all stars. O(1) Because Sqrt(32000)=O
(1)
> Update bucket! O(1)
>
> I used next:
> b[i] - number of start with x <= i.
>
> P.S. Bucket may be any size. For speed I chose bucket size 128. So
I
> fastly can find bucket num: x shr 7.
>
> If something explained badly, ask.
>
> Good luck!

thanks a lot for your help. (sory about previous message)

but can you explain in detail what do you put in buckets :
a range of star in sorted list, or a list of star which X coordinate
is in some range ?

why sqrt(N) - amount of buckets ?
in placing id a star do you mean calculation of its level ?

> but can you explain in detail what do you put in buckets :
> a range of star in sorted list, or a list of star which X
coordinate
> is in some range ?

Picture:
^y
|                 * <- we currently process this star
|  *      *        *
|  *         *
|     100      200     300
|      |        |       |    x
+--------------------------->
 \_____/\______/\______/\___
bucket0 bucket1 bucket2  etc.
  2        2     1 (!)


We store in bucket amount of stars with x coordinate in range;

To make it faster to analyze I used next statement: "two integers X
and Y per line separated by a space, 0<=X,Y<=32000".

Let b[i] = bucket i. b is array of integer;
Let p[k] = Number of stars wich x coord is k
Let Size = size of bucket. We select this value as we want.
It is easy to see that we will have (32000 + 1)/Size + 1 buckets.

The read and solve pseudo code:
1. b[i] = 0 for each i = 0, 1, .... (MaxX+1) div size + 1
   p[i] = 0 for each i = 0, 1, 2, ... , 32000
2. We read star with coords (x; y)
3. CurLevel = 0
4. CurBucket = x div Size;
5. for i = 0 to CurBucket-1 do CurLevel = CurLevel + b[i];
   Explanation: Because in bucket i (<CurBucket) we have number of
stars with smaller x than current star we avoided running whole
coordinates array.
6. But there still can be start with smaller x and wich are in same
bucket!
   for i := (x div Size) * Size to x do
         Inc(CurLevel, p[i]);
   Left bound is leftest element in bucket. Right bound is coordinate.
7. Print CurLevel.
8. We need to upgrade buckets.
   Inc(b[CurBucket]);   <--- New star in bucket !
   Inc(p[x]);           <--- New star on x !
9. Anything left?

About size of buckets. If we use too small bucket size we will do a
lot of job on p.5.  If we use too big bucket size we will do a lot of
job on p.6.
So we have to find such Size that next expression is minimal:
   32000/Size  +  Size    >= 2 * Sqrt(32000/Size  *  Size)        =
                    (&#1090;&#1077;&#1086;&#1088;&#1077;&#1084;&#1072; &#1050;&#1086;&#1096;&#1110;, &#1103;&#1082; &#1087;&#1086; &#1072;&#1085;&#1075;&#1083;&#1110;&#1081;&#1089;&#1100;&#1082;&#1080; &#1085;&#1077; &#1079;&#1085;&#1072;&#1102; :( )
=  2 * Sqrt(32000) ~ 358.
   To make this expression as small as possible it must be:
   32000/Size = Size   => Size = Sqrt(32000)

To be as strict as possible this solution is O(N) because number of
buckets is constant :). &#1040;&#1083;&#1077; &#1088;&#1091;&#1082;&#1072; &#1085;&#1077; &#1087;&#1110;&#1076;&#1085;&#1110;&#1084;&#1072;&#1108;&#1090;&#1100;&#1089;&#1103; &#1085;&#1072;&#1079;&#1074;&#1072;&#1090;&#1080; &#1081;&#1086;&#1075;&#1086;
&#1083;&#1110;&#1085;&#1110;&#1081;&#1085;&#1080;&#1084;!.

The O(N * Sqrt(N)) mark is taken from problem 1090 "In the army now".
Number of buckets there is Sqrt(N).  If you read this 2 problems you
might see that they are very similar, execpt soldiers cant have same
height. Level of star is number of jumps made by soldier :).

&#1076;&#1091;&#1078;&#1077; &#1076;&#1103;&#1082;&#1091;&#1102; ) thanks a lot.

but how be in following situation :

Picture:
^y
|           *     *
|  *      *        * <- we currently process this star
|  *         *
|     100      200     300
|      |        |       |    x
+--------------------------->
 \_____/\______/\______/\___
bucket0 bucket1 bucket2  etc.
  2        2     1 (!)

we insert star in bucket #2, calculating level of it
 = b[0]+b[1]+p[200..x]
while there is star in bucket #1 which Y coord > Y coord of current
star.?

thanks for your help.
i got AC in 0.7 sec. maybe because i used another partition in
buckets not on x ranges, but on star ranges, and the constant of my
algo is bigger than your one.

i tried also to solve this problem using sorted binary tree. (
insertation & finding the star level aproximately log2(n) ), but i
got TLE (maybe there is a test with all stars with equal X?).

sorry about offtopic, but do you take part in ACM Ukrainian Regional
Contest on 2-5 March ?

thanks for your help.
i got AC in 0.7 sec. maybe because i used another partition in
buckets not on x ranges, but on star ranges, and the constant of my
algo is bigger than your one.

i tried also to solve this problem using sorted binary tree. (
insertation & finding the star level aproximately log2(n) ), but i
got TLE (maybe there is a test with all stars with equal X?).

sorry about offtopic, but do you take part in ACM Ukrainian Regional
Contest on 2-5 March ?

ACM Ukrainian Regional, what is this. Is it NetOI?
I am in 9-th form. I take part in Ukrainian Respublican Olimpiad
(UOI). How old are you?

I used partitioning by x with bucket size 128. This made selecting
bucket slightly faster: x shr 7 = x div 128.

ACM Ukrainian Regional is 1/8 of final ACM world students command
olympiad. Ukraine is devided on 4 regions. One of them is Kiev region.
it covers several districts.

Are from Kiev ? (in this case maybe you could take part in Kiev
Regional olympiad (not included in rating), i am one of its
organizers and participant as well:)

i am a student of NAU on 3-d course

my mail : xdex@ukrpost.net
send me ur src.

Use HeshList !!!!

Hi!
I solved this problem, but I have some trouble with 1090, which as
you said, is simillar. I can't realize why I get WA. I posted my code
at 1090's webboard... If you could look over my code or give me some
test cases I would be grateful. My e-mail is vlad_io1@yahoo.com

Any balanced trees! Not RB! RB is hard to implement in contest!