[BOJ] 14434 : 놀이기구1

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 2e5 + 3;

int N, M, K, Q;
int lim[MAX], ans[MAX];
vector<int> grow[MAX];

inline int get_sum(int u, int v, int k) {
	int ret1 = upper_bound(grow[u].begin(), grow[u].end(), k) - grow[u].begin();
	int ret2 = upper_bound(grow[v].begin(), grow[v].end(), k) - grow[v].begin();
	return ret1 + ret2;
}

int main() {
	scanf("%d %d %d %d", &N, &M, &K, &Q);
	for (int i = 1; i <= M; ++i) {
		scanf("%d", &lim[i]);
	}
	for (int i = 1; i <= K; ++i) {
		int a;
		scanf("%d", &a);
		grow[a].push_back(i);
	}

	for (int i = 1; i <= Q; ++i) {
		int u, v, k, res;
		scanf("%d %d %d", &u, &v, &k);
		int left = 1, right = K;
		if (get_sum(u, v, K) < lim[k]) res = K + 1;
		else {
			while (left <= right) {
				int mid = (left + right) / 2;
				if (get_sum(u, v, mid) < lim[k]) left = mid + 1;
				else res = mid, right = mid - 1;
			}
		}
		ans[res] += 1;
	}

	for (int i = 1; i <= K; ++i) {
		ans[i] += ans[i - 1];
		printf("%d\n", ans[i]);
	}

	return 0;
}