I'd found a test like this. =)

For test:
36
1 1
2 2
3 2
4 3
5 3
6 3
7 4
8 4
9 4
10 4
11 5
12 5
13 5
14 5
15 5
16 6
17 6
18 6
19 6
20 6
21 6
22 7
23 7
24 7
25 7
26 7
27 7
28 7
29 8
30 8
31 8
32 8
33 8
34 8
35 8
36 8

my prog, that uses just sort() gives answer
36 8
35 8
...

and it answered correct when i used stable_sort() with same compare function:
29 8
30 8
...

After that i suppose to write new compare function, using indexes
struct state
{
  int id, m, ind; // << ind is a new param
};
bool compare( state a, state b )
{
    if ( a.m == b.m )
        return a.ind < b.ind;
    return a.m > b.m;
}

So watch at the results of my work:

sort()
WA#4

stable_sort()
AC 0.187s 1885 KB

sort() + ind
AC 0.218s 1897 KB

So we can say, stable_sort uses equal amount of additional memory, as like we use standard sort and indexes,
but at this dataset stable_sort works a little quicker!

stable_sort() + ind (i made it for lulz)
AC 0.203 2769 KB

Still quicker, than sort! =)

Counting sort
AC 0.125 1233 KB

;)

And after some zhest' optimizations...

AC 0.062 1225 KB %) %)

Thanks, it helped much!

2^31-1 = 2'147'483'647
(2^31-1) * 2 = 4'294'967'294

overflow is when you do this:

[(2^31-1) + (2^31-1)] / 2 = (4'294'967'294) / 2 = 2^31-1

My program successfully passes these tests but still has WA#5 :(

thank you!I overlooked this point ……

thank you)

Sended ...

Thanks e-maxx!!!
AC whithout precalculating http://pastebin.com/d9UX3xh2