do you know why you got so many downvotes?

Please, Update Score distribution.

Hope to see you GM post this round, Best of luck :P

Well lots of bit manipulation is already going on in comment section.. damn they are already practicing for the problem.. BitForces

bad round, no pikachu theme...

Post Script.

Yes, exactly.

I thought it is always you :)

gepardo

Umm... Not you this time?

NOTED

I wonder if I get negative contribution, will it balance out and give me positive delta

Thank you for teaching me English! You have taught me how to write the verb taught!

Actually, it is not mine, just google it.

Исправил, спасибо.

Well, you are kind of correct: tasks D1 and D2 require a correct solution.

Why not?Every A of CF is easy!Sometimes it looks harder but has an easy solution.Like last round's A was pretty easy.But most of us thought that bruteforce wouldnt work :(

Editorials will be provided only on English and Russian, I think :)

Right after the system testing I guess.

I didn't submit anything for the contest, but I think you might be able to keep the indices of positive/negative in a set, get the lower and upper bound for each query in logn, and just greedily pick from there.

Much easier :)

From D1 you should already know, that answer is always $$$1$$$ for odd segments and $$$2$$$ for even, if sum inside is not equal $$$0$$$. So, firstly we will reduce problem to odd segments by taking first element of even segment to answer, for example. Then, you need to find such element, that sums before it and after in segment the same. Suppose we have query $$$[l, r]$$$ and we want to delete element $$$x$$$. In terms of prefix sums we will get $$$pref[r] - pref[x] = pref[x- 1] - pref[l - 1]$$$, that equals to $$$pref[x - 1] + pref[x] = pref[l - 1] + pref[r]$$$. And all you need — is to count $$$pref[x] + pref[x - 1]$$$ for all elements and add to some associative container such indexes, let's call it $$$C$$$. The answer- lower_bound in $$$C[pref[l - 1] + pref[r]]$$$ by $$$l$$$. 127111849

fr

Broo exactly!

I can think of O(n^2 logn). But I don't think that's meant to pass.

Wait for editorial :)

I used suffix array with an O(N^2) dp, got the pattern when writing out the suffix array of the first sample test and try to get the result from that.

I tried an O(n^2) dp approach. solution

I utilised the fact that the answer for the reverse of the expansion will be the longest decreasing subsequence.

By reversing the string, we can enumerate all the substrings that end at any particular character such that they are in the same order as in the original expansion.

Now let dp[i] be the LDS such that we necessarily took the substring ending with char s[i].

So for calculating dp[i], the answer will be at least i+1 as we can take all the substrings ending at s[i]. Now we can iterate and check if we can add all these substrings to any previous answer only if those answers are greater than all substrings ending at s[i] (as it's always best to include these substrings).

SO to check two substring families ending at s[j] and s[i] (j < i), I pre-calculated g[j][i] which tells me after which length of a substring starting from j towards 0, it becomes greater than the substring family s[i] and use this value to subtract the initial substrings starting at j which are smaller than substring family s[i].

Now final answer is max of all dp[i]

PS:- sorry for my bad explanation.

Greedy .... lets say you have a string 1101 which is x (let's say) then to get a number that dividides it is simply 11010 which is 2 * x

So basically all we need is a 0 to find a multiple .... let place = index of last 0 (from 1 to n)

Case 1 — 0 exist in 1 to n/2 then just print from that place where 0 is to n and place+1 to n

Case 2- 0 exist after n/2 then print 1 to place , 1 to place -1

case 3- 0 is at n/2 ... print from n/2 to n and n/2+1 to n

Case 4 — all numbers are 1 ... then print 1 to n/2 and n/2 to n or 1 to n/2 , 2 to n/2+1

Yes

Problem name of this problem is a big hint to reveal the same.

NOTED