14434번: 놀이기구1

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

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MX = 2e5;
int n, m, k, q, cnt[MX + 1], l[MX + 1], r[MX];
vector<int> v[MX + 1], idx[MX + 1];
int f(int x, int y, int z) {
    int low = 0, up = k - 1, mid;
    while (low <= up) {
        mid = (low + up) / 2;
        int px = upper_bound(idx[x].begin(), idx[x].end(), mid) - idx[x].begin() - 1,
            py = upper_bound(idx[y].begin(), idx[y].end(), mid) - idx[y].begin() - 1;
        v[x][px] + v[y][py] >= z ? up = mid - 1 : low = mid + 1;
    }
    return low;
}
int main() {
    scanf("%d%d%d%d", &n, &m, &k, &q);
    for (int i = 1; i <= m; i++) scanf("%d", l + i);
    for (int i = 1; i <= n; i++) v[i].push_back(0), idx[i].push_back(0);
    for (int i = 0, x; i < k; i++) {
        scanf("%d", &x);
        v[x].push_back(++cnt[x]);
        idx[x].push_back(i);
    }
    for (int i = 0, x, y, z; i < q; i++) {
        scanf("%d%d%d", &x, &y, &z);
        r[f(x, y, l[z])]++;
    }
    for (int i = 0, s = 0; i < k; i++) {
        printf("%d\n", s += r[i]);
    }
    return 0;
}