Cách dùng lower_bound() và upper_bound() cho vector<pair<int, int>> theo .first hoặc .second?

[minhcanhtu (Secret)]

Hi mọi người. Mình có đang giải 1 problem sau: http://ntucoder.net/Problem/Details/2252
Mình sẽ tạo 1 vector<pair<int, int>> để lưu trữ dữ liệu vào. Thuật toán của mình chỉ là đơn giản sort vector giảm dần theo pair.second. Sau đó, với một nhóm phần tử có cùng giá trị pair.second, mình sẽ sort giảm dần tiếp nhóm phần tử đó theo pair.fist và tính từ trên xuống cho ra KQ.
VD:

10
6 0
2 0
9 1
1 2
3 0
4 2
0 2
0 1
4 0
0 2

Sau 2 lần sort theo pair.second và pair.first ta sẽ được:

4 2
1 2
0 2
0 2
9 1
0 1
6 0
4 0
3 0
2 0

Lúc này chỉ việc tính từ trên xuống dưới, dừng khi b_i = 0, ta sẽ được output là 29.
Nhưng mình gặp khó khăn ở phần cài thuật toán, cụ thể là sau khi sort xong pair.second, mình sẽ bắt đầu sort pair.first cho từng nhóm phần tử. Mình lọc ra nhóm phần tử có chung giá trị pair.second bằng lower_bound và uppper_bound nhưng ở đây là vector<pair<int, int>> nên mình để:

auto first = lower_bound(v.begin(), v.end(), val);
auto last = upper_bound(v.begin(), v.end(), val);

thì không hoạt động.
Mọi người có thể hướng dẫn cho mình chỗ này được không ạ?
Xin cảm ơn.

[Nam_Nguyen14 (Nam Nguyen)]

Tại sao bạn không sort trong một lần luôn mà phải sort đến hai lần nhỉ?

#include <vector>
#include <utility>
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    vector<pair<int, int>> redPackets = { {6, 0}, {2,0}, {9, 1}, {1, 2}, {3, 0}, {4,2}, {0, 2}, {0, 1}, {4, 0}, {0, 2}};

    sort(redPackets.begin(),
         redPackets.end(),
         [](const pair<int, int>& a, const pair<int, int>& b)
         {
            if (a.second > b.second)
                return true;
            else
            {
                if (a.second < b.second)
                    return false;
                else
                    return a.first >= b.first;
            }
         });

    return 0;
}

[noname00 (HK boy)]

Dành cho ai không chơi C++ >= 11:

bool cmp_pair(pair<int, int> A, pair<int, int> B) {
    return (A.second > B.second || (A.second == B.second && A.first > B.first));
}

vector< pair<int, int> > vector_pair;

sort(vector_pair.begin(), vector_pair.end(), cmp_pair);

[minhcanhtu (Secret)]

Dành cho ai không chơi C++ >= 11:

This is what I need

std::sort có comparator mà bạn viết riêng rồi feed vào cũng được.

Tại sao bạn không sort trong một lần luôn mà phải sort đến hai lần nhỉ?

Ừm, nhưng lúc đó mình ko biết viết comparator để sort theo cả second và first mà chỉ biết viết để sort theo second à ! Nên nảy ra cái ý tưởng là sau khi sort theo second xong, dùng lower_bound và upper_bound để lấy ra 2 con iterators bỏ vào sort để sort theo first, giờ thì ok rồi !