BOJ 14434 놀이기구1

놀이기구1
(http://boj.kr/14434)

먼저, 날짜별로 구하는건 필연적으로 놀이기구들을 다 확인해야 돼서 힘들다고 생각했다.
그래서 놀이기구별로 언제부터 가능한지를 이분탐색으로 찾으려 했는데,
어떤 날에 두 아이의 키가 얼마인지를 바로 알려면 \(NK\)크기의 공간이 필요해서 필요한 것만 남기는 방법을 고민했다.
이 부분은 금방 알아냈다. 각 아이별로 키가 크는 시점만 저장해논 뒤, 이분탐색으로 현재 시점이 각 아이의 몇 번째 성장인지를 찾으면 된다.
이렇게 놀이기구가 가능한 날을 구한 뒤, 그 날의 카운트를 늘려주면 앞에서부터 답을 셀 수 있다

풀고나서 찾아보니 parallel binary search라는 기법이였다.
유성문제와 비교했을때 이 풀이가 pbs라고 하기엔 이상한 것 같다...

#include <bits/stdc++.h>
 
using namespace std;
 
int g[200001], ans[2000001];
vector<int> r[200001];
 
int main() {
    int n, m, k, q;
 
    scanf("%d %d %d %d", &n, &m, &k, &q);
 
    for (int i = 1;i <= m;++i)
        scanf("%d", &g[i]);
 
    for (int i = 1;i <= k;++i) {
        int u;
 
        scanf("%d", &u);
 
        r[u].push_back(i);
    }
 
    for (int i = 1;i <= q;++i) {
        int u, v, w;
 
        scanf("%d %d %d", &u, &v, &w);
 
        int left = 1, right = k, can = k + 1;
        while (left <= right) {
            int mid = (left + right) / 2;
 
            if ((upper_bound(r[u].begin(), r[u].end(), mid) - r[u].begin()) + (upper_bound(r[v].begin(), r[v].end(), mid) - r[v].begin()) >= g[w]) {
                can = min(can, mid);
                right = mid - 1;
            }
            else
                left = mid + 1;
        }
        
        ans[can]++;
    }
 
    int tot = 0;
    for (int i = 1;i <= k;++i) {
        tot += ans[i];
        printf("%d\n", tot);
    }
 
    return 0;
}