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://codeforces.net/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.

This is what I was about to go for, then made triplets using sruct lolol

Quite tough as a Prob.B :(

I got stuck with that for 40min, with three Wrong Answers.

How would you transition to a new index?

I pretty much got the same, including the mess and the fail at pretest 2 (and couldn't correct in time)

You can preprocess the intervals in order and map each interval to one of the available bits:

whichBit.resize(n,-1);
vector<bool> used(8,false);
for(int i=0;i<at.size();++i){
	for(auto interval:out[i])
		used[whichBit[interval]]=false;
	for(auto interval:in[i]){
		int bit=find(used.begin(),used.end(),false)-used.begin();
		whichBit[interval]=bit;
		used[bit]=true;
	}
}

If you want to set / unset an interval, you should use (1<<whichBit[interval]).

There is a similar problem on atcoder. But I couldn't remember problem-id. Maybe someone can find it.

well I find it, arc094b. but total score is $$$a*b$$$ not $$$a+b$$$, and $$$n\rightarrow\infty$$$

Haha :D

Me too ;-; I thought that B is always easier than C so I tried my best to solve it, and failed ;-;

Actually I spent almost 40 minutes on Problem A after I solved B & C. I did not see the condition that at most one portion is allowed, and was completely stuck.

D, can you explain sample test?

"In this case all children will be happy except the third." The third kid gets 3 candies, which is odd, so it should be happy. Kids 2 and 4 get two candies, should be unhappy. ???

Just use a monotonic stack.

What's wrong with the following code?

ll n,x,y; cin >> n >> x >> y;
    ll best,worst;
    if (x+y<=n) cout << 1 << " ";
    else
    {
        best=min(n,1+x+y-n);
        cout << best << " ";
    }
    if (x+y<=2) cout << 1;
    else
    {
        worst=min(n,1+x+y-2);
        cout << worst;
    }

linear dp + non-decreasing stack

The final array of the answer can of these 3 forms :

1). Non-decreasing order
2). Non-increasing order
3). Non-decreasing order upto some index i, then non-increasing order from i+1 to n.

Part 1 and 2 is straight forward. For 3rd part we will do some preprocessing. Let's construct two arrays Pre, Post.

Pre[i] will contain the number of floors we can make if the array is in non-decreasing order starting from 1 to i.
Post[i] will contain the number of floors we can make if the array is in non-increasing order starting from i to n.

let's calculate array Pre.

Consider 1 based indexing.
Pre[i] for a particular index will be (i - j) * arr[i] + Pre[j]. Here j is **largest** index of element which is smaller than arr[i] to the left of it. If no such j exists then j = 0. More formally, arr[j] < arr[i] and j < i. Index j can be calculated using stack.

Similarly Post array can be calculated. And the array will be splitted at the point where pre[i] + post[i+1] is maximum. See this for stack method.

haha, nice bro <3

;-; Sad for me trying all the O(1) formula I can think with no result

How can you solve B ?