7795번: 먹을 것인가 먹힐 것인가

https://www.acmicpc.net/problem/7795


$O(t(n\lg n+m))$

a[i]>b[j]인 (i,j) 쌍을 구하는 문제
a[0...n-1]을 오름차순 정렬한 다음,
각 j마다 b[j]보다 크면서 가장 작은 a[i]의 i를 p라고 할 때 n-p를 누적해준다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, a[20000], t;
int main() {
    for (scanf("%d", &t); t--;) {
        int r = 0;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%d", a + i);
        sort(a, a + n);
        for (int i = 0, x; i < m; i++) {
            scanf("%d", &x);
            r += n - (upper_bound(a, a + n, x) - a);
        }
        printf("%d\n", r);
    }
    return 0;
}