ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#6070

사탕 지팡이 축제 1s 1024MB

問題

농부 존의 소들은 상당한 간식 중독자로, 특히 사탕 지팡이를 먹는 것을 특히 즐깁니다! 농부 존은 N 마리의 소가 있으며 각 소는 특정한 초기 높이를 가지고 있습니다. 그리고 그는 각기 다른 높이의 M개의 사탕 지팡이로 그들을 먹이고 싶어합니다 (1\le N,M\le 2\cdot 10^5).

농부 존은 각각의 소에게 순서대로 사탕 지팡이를 먹이기로 계획하고 있습니다. 소에게 사탕 지팡이를 먹이려면 초기에 사탕 지팡이가 땅에 가깝게 매달려 있어야 합니다. 그런 다음 소들은 입력에서 주어진 순서대로 일렬로 줄을 서서 사탕 지팡이에 다가가서 각자의 높이까지 먹습니다 (그들은 더 높이 먹을 수 없습니다). 사탕 지팡이는 초기에 설정된 위치에 머물러 있고 소가 사탕 지팡이의 아래 부분을 먹은 후에도 땅으로 내려가지 않습니다. 사탕 지팡이의 기둥이 이미 소의 높이보다 높은 경우 해당 소는 아무 것도 먹지 않을 수 있습니다. 각 소가 차례로 먹은 후에는 소의 높이가 먹은 사탕 지팡이의 단위 수만큼 증가하고, 농부 존은 다음 사탕 지팡이를 매달고 소들이 프로세스를 반복하게 됩니다 (다시 소 1이 다음 사탕 지팡이를 먹기 시작함).


入力

첫 번째 줄에는 N과 M이 주어집니다.

다음 줄에는 N 마리의 소의 초기 높이가 각각 [1,10^9] 범위로 주어집니다.

다음 줄에는 M 개의 사탕 지팡이의 높이가 각각 [1,10^9] 범위로 주어집니다.


出力

각각의 N 마리 소의 최종 높이를 개별 줄에 출력합니다.

이 문제에서 사용되는 정수의 크기가 크기 때문에 64비트 정수 데이터 유형(예: C/C++에서의 "long long")을 사용해야 할 수 있습니다.


例題 

3 2
3 2 5
6 1
7
2
7

첫 번째 사탕 지팡이의 높이는 6입니다.

첫 번째 소는 첫 번째 사탕 지팡이의 높이 3까지를 먹은 후, 첫 번째 사탕 지팡이의 나머지 부분이 높이 [3,6]을 차지하게 됩니다. 두 번째 소는 첫 번째 사탕 지팡이의 나머지 부분을 아무것도 먹을 수 없습니다. 세 번째 소는 첫 번째 사탕 지팡이의 두 단위를 추가로 먹습니다. 농부 존은 첫 번째 사탕 지팡이의 나머지 부분이 높이 [5,6]에 있지만 아무도 먹지 않습니다. 그 다음 각 소는 먹은 양만큼 성장하므로 소의 높이는 [3+3, 2+0, 5+2]=[6, 2, 7]이 됩니다.

두 번째 사탕 지팡이의 높이는 1이며, 첫 번째 소는 모두 먹습니다.



出典

USACO 2023 December Bronze

ログインしないとコードを書けません。