27543번 - 鐘 (Bell) 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 52 | 32 | 27 | 62.791% |
문제
JOI 市には 1 本の十分に長い道路がある．この道路は数直線とみなすことができ，各地点は 1 個の実数による座標で表される．
また，JOI 市にはこの道路に沿って N 個の鐘があり，座標の小さい順に 1 から N までの番号が付けられている．鐘 i (1 ≦ i ≦ N) は座標 Ai にある．
JOI 市では，1 年の終わりにこれらの鐘を一斉に鳴らすのが一大イベントとなっている．
どの鐘も，鳴らすとその鐘と同じ地点では強さ K の音で聞こえるが，距離が 1 離れるごとに聞こえる音の強さは 1 小さくなり，距離が K 以上離れると 0 になる．すなわち，鐘 i を鳴らしたとき，座標 x で聞こえる鐘 i の音の強さは max{ K - |x - Ai|, 0 } である．ただし，|t| は t の絶対値を表す．
すべての鐘を鳴らしたとき，座標 x で聞こえる鐘の音の強さは，座標 x で聞こえるそれぞれの鐘の音の強さの最大値である．
JOI 市にはこの道路に沿って M 個の家があり，古い方から順に 1 から M までの番号が付けられている．家 j (1 ≦ j ≦ M) は座標 Bj にある．
JOI 市の市長であるあなたは，すべての鐘を鳴らしたとき，それぞれの家で聞こえる鐘の音の強さを知りたい．
JOI 市の鐘と家の情報が与えられたとき，すべての鐘を鳴らしたときに座標 B1, B2, …, BM で聞こえる鐘の音の強さを求めるプログラムを作成せよ．
입력
入力は以下の形式で与えられる．
N M K A1 A2 … AN B1 B2 … BM
출력
M 行出力せよ．j 行目 (1 ≦ j ≦ M) には，すべての鐘を鳴らしたときに座標 Bj で聞こえる鐘の音の強さを出力せよ．
제한
- 1 ≦ N ≦ 250 000．
- 1 ≦ M ≦ 250 000．
- 1 ≦ K ≦ 109．
- 0 ≦ Ai ≦ 109 (1 ≦ i ≦ N)．
- Ai ＜ Ai+1 (1 ≦ i ≦ N - 1)．
- 0 ≦ Bj ≦ 109 (1 ≦ j ≦ M)．
- Bj ≠ Bk (1 ≦ j ＜ k ≦ M)．
- 入力される値はすべて整数である．
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | N = 1，M ≦ 1 000． |
| 2 | 20 | N ≦ 1 000，M ≦ 1 000． |
| 3 | 60 | 追加の制約はない． |
예제 입력 1
1 5 10 20 20 15 28 10 32
예제 출력 1
10 5 2 0 0
この入力例では，座標 20 に鐘 1 がある．
- 鐘 1 を鳴らしたとき，座標 20 で聞こえる鐘 1 の音の強さは max{ 10 - |20 - 20|, 0 } = 10 である．したがって，1 行目には 10 を出力する．
- 鐘 1 を鳴らしたとき，座標 15 で聞こえる鐘 1 の音の強さは max{10 - |15 - 20|, 0 } = 5 である．したがって，2 行目には 5 を出力する．
- 鐘 1 を鳴らしたとき，座標 28 で聞こえる鐘 1 の音の強さは max{10 - |28 - 20|, 0 } = 2 である．したがって，3 行目には 2 を出力する．
- 鐘 1 を鳴らしたとき，座標 10 で聞こえる鐘 1 の音の強さは max{10 - |10 - 20|, 0 } = 0 である．したがって，4 行目には 0 を出力する．
- 鐘 1 を鳴らしたとき，座標 32 で聞こえる鐘 1 の音の強さは max{10 - |32 - 20|, 0 } = 0 である．したがって，5 行目には 0 を出力する．
この入力例はすべての小課題の制約を満たす．
예제 입력 2
3 4 100 116 194 258 57 155 222 360
예제 출력 2
41 61 72 0
- 鐘 1,2,3 を鳴らしたとき，座標 57 で聞こえる音の強さはそれぞれ 41,0,0 である．したがって，すべての鐘を鳴らしたときに座標 57 で聞こえる音の強さはこれらの最大値である 41 である．そのため，1 行目には 41 を出力する．
- 鐘 1,2,3 を鳴らしたとき，座標 155 で聞こえる音の強さはそれぞれ 61,61,0 である．したがって，すべての鐘を鳴らしたときに座標 155 で聞こえる音の強さはこれらの最大値である 61 である．そのため，2 行目には 61 を出力する．
- 鐘 1,2,3 を鳴らしたとき，座標 222 で聞こえる音の強さはそれぞれ 0,72,64 である．したがって，すべての鐘を鳴らしたときに座標 222 で聞こえる音の強さはこれらの最大値である 72 である．そのため，3 行目には 72 を出力する．
- 鐘 1,2,3 を鳴らしたとき，座標 360 で聞こえる音の強さはそれぞれ 0,0,0 である．したがって，すべての鐘を鳴らしたときに座標 360 で聞こえる音の強さはこれらの最大値である 0 である．そのため，4 行目には 0 を出力する．
この入力例は小課題 2, 3 の制約を満たす．
예제 입력 3
10 10 10000 589 2398 6567 28817 29177 31636 45468 66751 82282 97509 2196 54498 80474 61644 18007 38759 85590 72172 79533 69959
예제 출력 3
9798 970 8192 4893 0 3291 6692 4579 7251 6792
この入力例は小課題 2, 3 の制約を満たす．
출처
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics for Girls > JOIG 2022/2023 3번
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호