시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 36 7 7 38.889%

문제

1번부터 N번까지 번호가 매겨져있는 총 N명의 아이들이 있다. 아이들은 놀이공원에 가는걸 좋아하지만 아이들은 키제한 때문에 타지 못하는 일이 빈번하다. 놀이기구는 1번부터 M번까지 총 M개가 있으며, 모든 놀이기구는 정원이 2명이다.

아이 i와 아이 j가 함께 놀이기구 k를 타려면, (아이 i의 키) + (아이 j의 키) >= (놀이기구 k의 키제한) 이 성립해야한다.

이러한 (i, j, k) 쌍이 Q개 주어지는데, 이 뜻은 아이 i와 아이 j가 놀이기구 k를 타려고 매일 시도한다는 뜻이다. 아이들의 처음 키는 모두 0cm이기 때문에 처음에는 모두 놀이기구를 타지 못하지만, 아이들은 성장기이므로 키가 쑥쑥 자란다. 구체적으로, 첫날부터 K번째 날까지 매일매일 한명씩 키가 1씩 자라게 된다.

그런데 이 문제에서는 아이들의 성장세가 무섭다! 만약 (아이들이 전날 놀이기구를 탄 횟수) > (아이들이 전전날 놀이기구를 탄 횟수) 라면, 키가 1이 아니라 2만큼 자라게 된다. 단, 첫째 날과 둘째 날에는 해당되지 않는다. 매일매일 누구의 키가 자라는지 주어질 때, 첫날부터 K번째 날까지 각 날마다 아이들이 놀이기구를 총 몇번 타는지 출력하는 프로그램을 작성하여라. (단, 놀이기구를 타는 것 보다 키가 자라는 것이 먼저 일어난다)

입력

첫째 줄에 아이들의 수 N, 놀이기구의 수 M, 기간 K, 질문의 갯수 Q가 주어진다. (1 <= N, M, K, Q <= 200,000)

둘째 줄에는 놀이기구들의 키제한이 순서대로 주어진다. (1 <= 키제한 <= 200,000)

셋째 줄에는 각 날에 키가 자라는 아이의 번호가 총 K개 주어진다. (1 <= 번호 <= N)

그 다음 Q줄에 걸쳐 (i, j, k) 쌍이 주어진다. (1 <= i, j <= N, 1 <= k <= M)

출력

K줄에 걸쳐 각 날마다 아이들이 놀이기구를 총 몇번 타는지 출력한다.

예제 입력 1

5 3 4 4
4 3 1
2 2 5 1
1 2 2
1 2 1
1 5 2
3 5 3

예제 출력 1

0
0
1
4

힌트

둘째날까지 아이들은 놀이기구를 타지 못한다.

셋째날에는 아이 3과 아이 5가 놀이기구 3을 탈 수 있다.

넷째날에는 아이 3과 아이 5가 놀이기구 3을 탈 수 있고, 아이 1과 아이 2가 놀이기구 1, 2를 탈 수 있고, 아이 1과 아이 5가 놀이기구 2를 탈 수 있다.

출처

High School > 선린인터넷고등학교 > 머그컵 H번