코드 복사/붙여넣기 하는 당신이 아름답습니다.

14434 : 놀이기구1

풀이

머그컵 문제!

parallel binary search를 사용하면 된다!

자세한 풀이는 여기에 있다.

헤헤 놀이기구2도 풀어봐야지

코드

#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;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2017-02-20 15:03

Read more posts by this author