[Codility] PassingCars

배열 A 내 원소값이 0인 인덱스를 P, 1인 인덱스를 Q라고 했을 때, (P < Q)를 만족하는 쌍의 개수를 구하는 문제.

upper_bound를 이용하면 P가 주어졌을 때, 유효한 Q의 개수를 바로 구할 수 있다.

https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

cpp code

#include <vector>
#include <algorithm>

int solution(vector<int> &A) {
    vector<int> P, Q;
    for (int i = 0; i < A.size(); i++) {
        if (!A[i]) P.push_back(i);
        else Q.push_back(i);
    }
    int ans = 0;
    for (int n : P) {
        auto ub = upper_bound(Q.begin(), Q.end(), n);
        ans += Q.end() - ub;
        if (ans > 1e9) return -1;
    }
    return ans;
}