백준 7795 먹을 것인가 먹힐 것인가

이번에 풀어본 문제는 7795 입니다.
문제:https://www.acmicpc.net/problem/7795
해당하는 문제는 A의 수 N이 주어지고 B의 수 M이 주어집니다.
N,M은 1보다 크거나 같고, 20,000보다 작거나 같습니다.
1초안에 풀어아 햐기 때문에, 브루트 포스로 풀 방법을 생각해보았는데, O(n^2) 로 시간초과가 날거 같았습니다.
순서를 변경해도 되기때문에, 이분탐색을 이용해 풀어보았습니다.

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

using namespace std;


int main(){
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);

    int c;
    int n,m;
    cin>>c;
    int cnt=0;


    int lt,mid,rt;
    while(c--){
        int res=0;
        cin>>n>>m;
        vector<int>a(n);
        vector<int>b(m);
        for(int i=0;i<n;i++){
            cin>>a[i];
        }

        for(int i=0;i<m;i++){
            cin>>b[i];
        }
        //오름차 정렬
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        cnt=0;
        for(int i=0;i<a.size();i++){
            lt=0;
            rt=(int)b.size()-1;
            while (lt<=rt) {
                mid=(rt+lt)/2;
                if(a[i]<=b[mid]){
                    rt=mid-1;
                }
                else{
                    lt=lt+1;
                    cnt++;

                }
            }

        }
        
        cout<<cnt<<"\n";


    }


    return 0;
}

풀어보니, lower_bound 를 이용한 풀이또한 가능할거 같아,lower_bound를 이용해서 풀어보았습니다.

//
//  7795_1.cpp
//  algo
//
//  Created by 박효정 on 2021/05/20.
//

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

using namespace std;


int main(){
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);

    int c;
    int n,m;
    cin>>c;
    int cnt=0;


    int lt,mid,rt;
    while(c--){
        int res=0;
        cin>>n>>m;
        vector<int>a(n);
        vector<int>b(m);
        for(int i=0;i<n;i++){
            cin>>a[i];
        }

        for(int i=0;i<m;i++){
            cin>>b[i];
        }
        //오름차 정렬
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        cnt=0;
        for(int i=0;i<a.size();i++){
            lt=0;
            rt=(int)b.size()-1;
            while (lt<=rt) {
                mid=(rt+lt)/2;
                if(a[i]<=b[mid]){
                    rt=mid-1;
                }
                else{
                    lt=lt+1;
                    cnt++;

                }
            }

           
          
            res+=(lower_bound(b.begin(), b.end(), a[i]))-b.begin();
        }
        
        cout<<res<<"\n";
        

    }


    return 0;
}