It's hard to see the round at this time.I hope it's easy.

Why are Chinese always ranting about start time smh ?

Yes, it's very friendly to the Indians as well.

Hope every Chinese who will take part in gets good grades

It can be a new contest format or something like global rounds(div.1+div.2)

of course :)

all the best :)

Keep pushing and Good Luck. You'll be the best. And I wanna becmoe purple too :).

How do you think about (1250+750)? Perhaps solution of Problem C will be short but difficult.

as lots of people can make div.2 problems, but div.1 is something else, much harder and much more important. also if you can make div.1, then you will add two simple problems to it, then it would be div.1 + div.2, but you cant add div.1 E/F that much easily. and its the reason that we dont have too many div.1 only rounds, but we have lots of div.2 + div.1 rounds and more div.2 rounds.

Because it's based on annual event; see round 342, 401, 466, 541.

have the same feeling :), what if we participate in this round as a warm up for the next one?

Disagreed. Cows aren't making problems garbage. I think they are making them easier to understand.

Например я :), Мой первый финал

The only way is to do your best in the contest.

Hope that I can solve C or D ;-;

That's goodbye rating for you my dear son.

Annoying B.

I love these "difficulty staircases" you make after every contest

haha :D

I cant solve B for 2 hours ;-; How stupid I am for a math problem

No, it is a horrible index fiddling with absolutly nothing to learn. You might be happy if you solve it, but that does not make it nice.

instead of seg tree do sparse table

For each position i you should calculate the total size of increasing buildings ending at that position.

Which is equvalent to the Next smaller element problem.

My solution is O(n), you can count all values using stack

Simply segment tree will do

No. It is sth like lineral dp + non-decreasing stack. The time complexity is O(n). Plus, I think n=500000 is aimed at preventing some O(nlogn) solution.

I used a different approach.

I built the cartesian tree of the array in O(n). Basically, each subtree represents a contiguous sub-array. And the root of a subtree is the index of the minimum element of the subarray. It's left and right childs are respectively the sub-array to the left, and to the right of the min.

Once I have that, I compute the solution for each subtree. Noticing that the buildings size must be constant either on the left subtree, or the right subtree. So I can calculate the answer in O(n) for all subtrees.

You can do binary search on the segtree and use logn time instead of log^2n. You can check my submission https://mirror.codeforces.com/contest/1313/submission/71698666

It can be done using a stack. First, we calculate the maximum score we can make from the left side (all buildings in non-decreasing heights) and the right side (all buildings in non -increasing heights). We can do this by maintaining a stack with increasing values. Then taking maximum among all index for left[index-1] + right[index].

Link

Try putting each element as peak element and the left part forms a increasing segment and the right part a decreasing segment, compute maximum answer for all peaks, and then take the maximum one.

Form min place let $$$lx = min(n-x-1, y - 1), ly = min(n - y - 1, x - 1)$$$. $$$Ans_{mn} = max( y-1-lx, x - 1- ly) + 1$$$. For max place $$$lx = min(n-x, y - 1), ly = min(n - y, x - 1)$$$. $$$Ans_{mx} = max( y-1-lx, x - 1- ly) + lx + ly + 1$$$. Maybe its too complicated, but I came with only this solution

What if A = N and B = N? you get (N + 1 N). I got WA on test 3 due to this case.

I only solve the second that

b = min(a, b - 1)

Is it wrong ?

int overflow

Just a guess, maybe something like this:

9
0 5 5 5 5 5 0 6 0 0

I also get WA in test 8.

I use the maximum number to construct answer, which is totally wrong. The flaw of my solution is that it can't detect the nearby situation and went wrong, like:

10 5 64 62 62 14 84 59 13 1 15

64 should be the summit of the answer, but I got 84.