Try greedily defeat more monsters, so we need to binary search how far we can reach.

Suppose we need to defeat K monsters and the highest power among them is P, we need to have at least one hero with p>=P and s>=K, which could be precalculated, in such a form: maxp_i = the largest power among heros which has s>=i. Thus we could easily check whether maxp_K>=P.

Binary search such K and get the answer, to find P, is a problem of RMQ，use ST.

code for B

The queries are a1*a2 a3*a4 a1*a3 a5*a5，It is possible to deduce a1 a2 a3 a4 from the first three queries and we got a5 by asking a5*a5, Then the array can be determined uniquely.

Indeed,sort use so called quicksort when n>16

while (true) {
    while (*__first < __pivot) // here always true
        ++__first;
    --__last;
    while (__pivot < *__last) // here always true
        --__last;
    if (!(__first < __last))
        return __first;
    iter_swap(__first, __last);
    ++__first;
}

Your cmp may cause out of bounds, so when n>16 it will RE.

UPD:use stable_sort instead?

Chinese version:sort在n>16的时候用通常意义上的快速排序，对于a<b且b>a这种情况(非偏序集?)，指针就跑飞了~

My fault.

But when cmp(a,b)==cmp(b,a)==true, sort will TLE.

I guess cmp was a bit not properly

cmp should return whether s1 should be in front of s2 in the result array or not according to your sort rules.

when a=b="aaa",cmp(a,b) and cmp(b,a) both be true.

try this case

7
6 1 1 6 1 1 6

Your output

5
2 1 3 5 4 7 6

Answer

5
2 1 3 4 5 7 6

What's more...I failed to analyze the code so no solution or reason to be provided. :(

I guess that your idea may be right.

Complexity Linear on the number of elements erased (destructions). Plus, depending on the particular library implemention, up to an additional linear time on the number of elements between position and one of the ends of the deque.

quote from:deque::erase

Maybe "multiset" XD

WOW, almost the same idea, I had just finished it! XD code

In C, sorry to tell that I just couldn't understand how to translate these mathematical language, could anyone please tell me the meaning in plain english?

What's more, the 't' here confused me, too.

UPD1:now I understand the 't', so stupid am I. XD