Although the problems are (very) similar, the one you linked does not ask the user to account for sequences of even length.

While a rather small difference, it's still worth noting.

Looks like you don't handle following case:

3

111

Answer is 1, your code will return 0.

Edit: or maybe you do, didn't see next for j loop. Will check with computer in an hour or so and come back with counterexample :)

Ok, found one (posting in another comment so you can get notification):

313

your code gives answer 1, but correct one is 2.

The execution time of a code is not exactly the same when you run it all the time. There are various factors for this. For example — server load(i think).

its strange but i just removed comments it got Accepted,don't know why

I just copy pasted your code (One which got TLE without any change) and submitted it and it got AC: 40215523

This is really strange.

Because max a[i] is 10^9. 2^29 < 10^9 < 2^30

Approach is similar to editorial, but Fenwick tree will be used to solve a subproblem that is required to calculate the answer. Let's say $$$g(x)$$$ is number of $$$(l,r)$$$ pairs such that median of subarray $$$a_l,a_{l+1},\cdots,a_{r}$$$ is greater than or equal to $$$x$$$. So the answer to the original problem will be $$$g(x)-g(x+1)$$$.

Now to calculate $$$g(x)$$$ let's create a new array $$$b$$$, where $$$b_i$$$ is $$$1$$$ if $$$a_i$$$ is greater than or equal to $$$x$$$ otherwise $$$b_i$$$ is $$$-1$$$. We know that for median to be greater than or equal to $$$x$$$ count of numbers greater than or equal to $$$x$$$ should be greater than the count of numbers less than $$$x$$$. Now the problem reduces to calculating number of subarrays in $$$b$$$ with positive sum. If $$$(l,r)$$$ is such a pair and $$$pre$$$ is the prefix sum array of $$$b$$$ then $$$pre[r]$$$>$$$pre[l-1]$$$. Now problem further reduces to counting for every index in $$$pre$$$ the count of numbers seen so far which are less than current number, which is a pretty standard problem that can be solved by Fenwick tree by adding one to all the numbers greater than $$$pre[i]$$$ before moving to $$$pre[i+1]$$$ and the count of such numbers will be the sum accumulated at that index. But here numbers can be negative so use an offset.

Here is my submission using Fenwick tree.

multiset::count is logarithmic in the size of the container, but linear in the number of matches. Test 26 seems to be a large array with only one number — the absolute worst case for your code, since it ends up with 30n² operations.

See http://www.cplusplus.com/reference/set/multiset/count/ for more details.

"If the length of the sequence is even, the left of two middle elements is used." Since the segment [2,4] is of even length, than the median will be the "left-middle" element. In this case 2.

M must be in the sequence because the median will be equal to one of the elements in seg[l..r].

You are talking about average. Problem asks for median. Those are different notions.

This helped me understanding the greedy solution, thanks. But there is actually no need to reverse the string, maybe that's why you couldn't understand the reason behind it. I couldn't find any reason or counter-example so I decided to submit without reversing and it got accepted.

Will you please explain the logic behind this snippet:

else if(szz(t) >= 18) t.erase(0,1);

I feel like description is quite good. Can you tell me if there is a part in explanation that you specifically don't understand? If it's even first sentence, that's fine, just say it, It will be easier to help you that way.

EDIT: negative votes for trying to help? Why? :)

std::map has guaranteed O(log N) complexity for search, insertion and deletion. It uses a comparison operator, and iteration happens in the order defined by that comparison operator.

std::unordered_map only guarantees O(N) complexity for search, insertion and deletion, but you normally expect it to be O(M), where M is (more or less) the size of an individual key. Assuming keys are small relative to the number of items, it's basically O(1).

if(mp[j-a[i]]>=1){ If map does not contain j - a[i] value, it will create it and your code will check new created values, what goes into TL.

To add to what Pi-nan said, while logn access would be completely fine for this problem normally, what is actually creating the problem is the way you're accessing the map. Checking if mp[j-a[i]] >= 1 will add the pair {j-a[i], 0} to the map if it doesn't already exist, and since that can happen many times, the size of the map can become very large. In that case, log(size_of_map) might actually be big enough to slow things down a bit, while the (amortized) O(1) access saved you in the second submission.

For reference, look at 40168171 — I've fixed your map code to not do this, and it's actually faster than the unfixed unordered_map, with the memory usage also being positively tiny in comparison (8000kB vs 170000kB)

Consider the case where median (or m as in input) is at the first index of array p. There should be increment in ans there for pair (1,1). But ans will remain 0, if u don't initiliase c[0] = 1. Take other cases like 1 3 2 (m=2). You will realise this is the requirement to consider the pair or segment from beginning to median i.e. 2 here. Infact, as sum = 0 initilally we have to take c[0] = 1 to take all values from beginnning to median or after median for first time where sum becomes 0.

Let us denote position of m in the array as pos.

We will be adding values to ans only for subarrays whose R (right index) is in the range [pos,n]. However, pos is a valid L (left index) as well, since it could be the starting index for a valid subarray. Hence they have used c[0] = 1. Let me know in case my explanation was unclear.

Because you are not considering the best value at z[i].. Consider the case s=1002 The output should be 2,but according to your logic you would get z[n]=1,thus neglecting the best value at z[n-1] which is 2.

Don't forget to do this : z[i] = z[i — 1] And then you want to maximize your answer so you do this z[i]=max(z[i], z[fin[r]] + 1). The point is that i-th number can either make answer bigger or not. So in case 11 you probably have already found best answer, but then did z[i]=z[fin[r]] + 1 and lost it.

no

So if we go along your thinking we should make all problems easier and easier to the point where all cases are just one big case and answer is always 42, right? :)

Also, I'm not sure if you can claim anything about time limit writing in Java without fast I/O. Maybe you should try looking at codes of top coders writing in Java and specifically at how do they deal with reading input if you really want to stick with using this language for Codeforces. Petr is probably your "go-to user".

it's basic DP. If you didn't understand this then don't worry first go and learn basic DP theory and solve some problems. Then come back, you will surely understand then that it's not that hard here.

Hey, writing just to let you know that someone here actually tried to help, so you are not alone :) Unfortunately I wasn't able to find main mistake, but few quick tips anyway:

a) don't use pow if you don't have to — you can achieve here the same result by doing a[i] = 2 * a[i-1]

b) don't use log2 if you don't have to — you can achieve here the same result by going through the number and checking number of bits set or just simply using __builtin_popcount (as you are using gcc)

c) it's just easier to declare a[40] or something like that and then checking all bits up to 31 always than making some error-prone code like the one with "max" and "c" — imho you are not gaining enough time/space to justify writing so much additional code just for that purpose

d) you have mistake for case with only one number 1 (although it's not why test case 8 doesn't work)

We do, I think you misunderstood concept. Array "c" contains sums for all possible left sides of the segments, so that's why we don't add there anything after reaching "m" as we cannot set left side after "m". Also, maybe my response here will help you:

http://codeforces.net/blog/entry/60511?#comment-444221

If not, please ask questions.

http://codeforces.net/blog/entry/60511?#comment-444221

Can you help me figure out what's wrong with my solution for D? It's similar to yours http://codeforces.net/contest/1005/submission/40252820

https://codeforces.net/blog/entry/60511?#comment-444221

If you go to your last solution, click on it's id, scroll down you will see test with wrong answer. It's very small, so you should be able to debug based on it. Have you done that?

Also, it's better to link your solution than paste code. Look at other comments.

http://www.cplusplus.com/reference/map/map/operator[]/

Comment below example: "Notice how the last access (to element 'd') inserts a new element in the map with that key and initialized to its default value (an empty string) even though it is accessed only to retrieve its value. Member function map::find does not produce this effect."

So when you do for example "hash[a[i] — it->first]" if "a[i] — it->first" is not in the map it will be inserted there with value 0, because that's how [] operator works on maps in cpp. You should use function "find" in this case.