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 %) %)