OJ Board

I think that, maximal possible K is 82. Because there are no numbers in inteval with larger sum of digits then 82.

I would like to know how the query can be answered directly on the union find datastructure.
It is interesting to me too.

I solved it just using LCA and calculated maximum edge cost from each vertex by 2^j vertices up.
Then each querry also can be answered in O(log n). Answer is the maximum value ...

Read the problem statement once again.

int for total cost is enought. We are not so cruel
Maximum answer is: 1766189.55$.

Maybe you used C not C++? I do not know how it works in C.
As far as C++ unsinged char must be used. Overway you will index array out of boundary and this is UB.

Yes, test input was copied. However it was resaved in ANSI encoding. So, I think that no characters higher then 255 have left.

I use gets() and vector of 255 elements.
If there was some unicode characters I think you sould get WA. Because my solution work only with char/usigned char [0..255].

char ch = 255;
ch is negative one !
but the clarification said that the character codes are non-negative.
"character value" In clarification means the amount of money paid for character. There is nothing said about character code. So codes may be in range of 0-225, and you must use usigned ...

Maybe somebody have some good testcases?

My algorithm work like this:
I make a plane at cone center that is penperdicular to xOy and our looking ray.
Then i am looking to a point of ray and plane intersection.
If this point is in segment interval, I check if its distance to a cone center axis is ...

I think line sweeping will help us.
Two intersecting rectangles will can always divide into three non intersecting ones. And non intersecting rectangles can be sorted by thier y value.

So let's sort rectangles by their X cordinate. Now we will hold examined rectanges in RBTree by their Y cordinnate ...

To sapnil:
Thanks, I had the same bug ))
However I think it must be a presentation error, but not WA.

And why do you get WA at first?
I also got WA, but do not know why....

run R1 is more OG than a run R2 if and only if:
R2 returns to the Green Line for the first time at an earlier point than when R1 returns to the Green Line, or

R1 and R2 return to the Green Line at the same point, but the portion of R1 to that point (ignoring the initial E and final S) is more OG ...

O(log(n)) time for 'c' query
O(n*log(n)) time for 'q' query
My n intervals work like this.
I think c is less then q, cause got AC only in more then 6sec.
2d interval tree works here.
Each query and update is O((log n)^2)
I know, however i would code it whole night :) It's enoght for me to have ...

I used N Interval Trees (a tree for each row) to get rather slow AC.
This is really nice problem, expcept for its statement.

"x1 y1 x2 y2" which represent the coordinates of the upper left and lower right of where you must calculate the maximum and minimum change in population.
"x y v" indicating a change of the population of city C [x, y] by value v.

q 1 1 2 3
c 2 3 10
q 1 1 5 5
q 1 2 2 2
Which input format is right ...

We have a segment consisting from other segmest.
For example second test: 1 1 10
We have segmens of length 12 (1+1+10).
Now we can make K cut, however we can cut(divide) segment only in places where it is connected.
With one cut from the previous segment we can get only 2(1+1) + 10 or 1 + 11(1+10 ...