Link to the problem is… Problem - C - Codeforces
Let Hi be a sorted sequence of hi. Let E — set of indices of the last elements of each block. Then for all e in E, first e sorted elements of sequence h_i are equal to the first e elements of the sequence H_j.
So, it is not difficult to notice that the size of E is the answer for the problem.
Firstly, we need to calculate two arrays: prefmax and suffmin, where prefmax(i) — maximum between a1, a2, …, ai, and suffmin(i) — minimum between ai, ai + 1, …, an.
If you want to get the answer, just calculate the number of indices i that prefmax(i) ≤ suffmin(i) + 1.
Time: O(N)
This is taken from the editorial of the contest. Take a look at it for clearer explanation
it can be solved greedily . if we are at the index ‘i’ and the maximum value of the current block is less than the minimum value with index > i , then we can terminate this block here and start a new block from the next index. So we calculate an array suf[i] which denotes the minimum of all values with index >= i , and we also maintain a variable which has the maximum of current block and then simulate this greedy algorithm. Here is my implementation Submission #14370937 - Codeforces