Thank you.

Or pupil >:)

If the tester was someone unrated (or a "newbie") would you refuse to participate?

thank you my good friend, wish you all the best!!!! may the best coder win

why so many downvote on this comment :o

How long did it take you to become a specialist?

Did Codeforces Round mean conducted on Codeforces? How about previous round such as 8VC Venture Cup 2016? No Codeforces stuff in its round name.

nice pp

What is the theory behind this?

Problems will be like As Blake is the CEO, he doesn't have time to solve this problem because he has bigger problems to solve, so he asks Chris

Don't worry, usually standard CF rounds don't use dynamic scoring.

Don't worry. Many got hacked!

you have your friends...

All I've came to:

You need to maximize value sum(A[j], A[j + 1], ..., A[i — 1]) — A[j](i — j) if i > j. Or value A[i] * (j — i) — sum(A[i + 1], A[i + 2], ..., A[j]) if i < j.

And print initialy characteristic + (diff > 0 ? diff : 0)

How to do this faster than O(n^2) I can't get:D

We iterate the array. For ith index we will find the best position j, left to the i (it could be right instead of left, but we will compute the right in another iteration), which maximizes (this equals to change of the value of the array when we move jth element to ith position).

As I said before we do the same thing (almost the same thing, equations are little different of course) for right. Then, the answer is the value of the original array + max(0, max of all changes).

To find the best j for a particular i, we need to fiddle with the equations a little and represent every element as a linear line:

ps[0] =  - ar[0]

ps[i] = ps[i - 1] - ar[i]

max_{1 ≤ j < i}{ps[i] - ps[j] - ar[j] * j + ar[j] * i} = ps[i] + max_{1 ≤ j < i}{( - ps[j] - ar[j] * j) + ar[j] * i}

Now we can represent ith element as a linear line. ith line equals to y = ar[i] * x + ( - ps[i] - ar[i] * i).

We first add the line 1. We then start iterating from index 2. When we're done with i (computed the result for it), we add the line i to our structure.

(To find the result for that position) When we're at a new position, let's again call it as i, we find the line which has the highest value for x = i. We also need to increase this value by ps[i].

To find the best line, we can use the convex hull trick on a segment tree, since slopes aren't non-decreasing like in the case of traditional convex hull trick.

Time complexity: O(NlogN)

I did it with segment tree+two pointer. Phew! Lot of confusing code

What I did:

Found the maximum number of sorted elements from all queries, from 0 to x

Sorted [0,x]

Then from that query looped to the end of the queires reversing the array from 0 to query's length, keeping track of what order was used last time. If the order changed, then reversed the array, otherwise did nothing.

I simply took maximums of type_1 query and type_2 query except for the last query, if in case last query is for type_1 then i first sorted max(type_2) in non-descending order and then sorted max(type_1) in non ascending order,and vice versa for the type_2 query in the last query. hope it works... :)

Check for overflow in your solution. Test 14 is a big one.

I used Z-function

I think a lot of them would fail System Test

From your earlier comment it seems that your solution is more complicated that it needs to be.

I tried to hack for int overflow in A. But I am stupid there will be no int overflow. In B, I tried hacking TLE submissions but i failed! :(

B: If you update the grid after each operation, worst-case complexity is O(k * max(n, m)).

Same there:D

i was able to hack with this test case

cout << 5000 << ' ' << 20 << ' ' << 100000 << endl;
forall(i,0,100000){
	cout << 2 << ' ' << 2 << ' ' << 2 << endl;
}

I hacked 8 solution in n=5000 k = 100000 case :)

Good estimation is 10^9 ops per second (from my experience).

What's that special test case that failed 10 solutions?? o.O

May be something like this:

3 3 3-a 2-b 3-a 1-a 2-b 2-a

Let's assume we have instruction 1-n. Everything before that instruction doesn't matter. So let's find the last instruction 1/2 — n. If that doesn't exist the number stays the same, if it does we have to take the smallest or the largest number in the array. After that we search for 1/2 (n-1) that is after our previous instruction and do the same process, but we also have to remember what was the last instruction that was made(if it was 1 or 2 so we know what number do we have to search for). We can sort the instructions and also use the set to get maximum/minimum and to remove elements(after we have used them already) so the complexity is O( (n+m) (log n + log m))

Give me five!) It taken 10 minutes to understand why WA2

Me too :)

I did it initially. But soon I could realize when sample test cases didn't pass on my local machine

SunitSwn

Lol same here. i even submitted the solution with an O(n**2) solution, but luckily it failed in pretest 1 only :P

Yes. I even asked an official clarification question so everybody can permanently see in the problem history how dumb I was.

Official answer was "There is no XOR. There is only OR. You are a fool."

(Part of it was not written but clearly implied).

Same!

My hopes are broken(((

I too was disappointed. May be n.m <= 100000 should be alright. Why n,m <= 5000?

This was done to ensure that the solution should pass on a Python.

I don't think it is a good idea to go for C+ right away if you are below like red or something.

But it is a good idea after solving first easy tasks (A, B and sometimes C) to read all others.

I only read C first in rounds which have both div 1 and div 2. For rounds with div 2 only like this, C is usually harder.

and after the system test, a lot of people failed on C which I passed. If only my brain worked 1 min faster :/ I just had to submit B (even the code was complete) :/

The tight input limit is somehow silly, why they didn't make it something like 1<=n, m<= 10^5 ,If they want a better algorithm.

without submitting a solution?

As I know on codeforces time limits are the same for all programming languages.