8217번 - 유성 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 256 MB | 2098 | 611 | 383 | 23.100% |
문제
최근 '백준 우주 연합(BIU)'은 어떤 은하계 근처에서 새로운 행성 하나를 발견했다. 그 행성은 유성우가 많이 내려 사람이 살기엔 적절치 못한 곳이었으나, 유성우에 관한 연구 대상으로는 아주 좋은 곳으로 밝혀졌다.
BIU 회원국은 이미 그 행성 가까이에 우주정거장을 세웠다. 이 우주 정거장의 목적은 유성우의 운석 샘플을 채취하는 것이다. BIU 연합 최고 지도 사령관인 백준은 행성 궤도를 M개의 구역으로 나누고 1부터 M까지 순서대로 번호를 부여했다. (행성 궤도는 원 궤도이므로 1번 구역과 M번 구역은 서로 인접해 있다.) 각 구역은 N개의 BIU회원국들이 서로 적당히 나누어 가졌다.
각 BIU 회원국들은 모으고자 하는 운석 샘플의 목표치를 정했다. 당신의 임무는 유성우 예보를 바탕으로 각 나라들이 언제 샘플 채취를 완료할 수 있는지 말해주는 것이다.
입력
첫째 줄에 두 정수 N, M (1 ≤ N, M ≤ 300,000)이 주어진다. N은 BIU연합의 회원국 개수고, M은 행성 궤도의 구역 개수이다.
둘째 줄에는 M개의 정수 oi (1 ≤ oi ≤ N)가 주어진다. oi는 i번째 구역을 소유하고 있는 BIU연합의 회원국 번호를 나타낸다.
세 번째 줄에는 N개의 정수 pj (1 ≤ pj ≤ 109)가 주어진다. pj는 j번째 BIU회원국이 목표치로 정한 운석 샘플 수량을 나타낸다.
네 번째 줄에는 정수 Q (1 ≤ Q ≤ 300,000)가 주어진다. Q는 유성우 예보의 수를 나타낸다.
다음 Q개의 줄에는 예측된 유성우의 개수가 날짜 순서로 표시된다. 각 u번째 줄은 세 가지 정수 lu, ru, au로 구성되는데, lu ≤ ru인 경우 구역 lu,lu+1,…,ru에 au개의 운석이 내리고, lu>ru인 경우 구역 lu,lu+1,…,m,1,…,ru에 각 구역당 au개의 운석이 내린다는 뜻이다. (정수 au의 범위는 1 ≤ au ≤ 109 이고, 여기서 u는 유성우 예보 시작 후 u번째 날을 의미한다.)
출력
회원국별로 샘플조사를 끝마칠 수 있는 최소 일 수 wj를 회원국 번호 순서대로 한 줄에 하나씩 출력한다. 끝마치는 날에는 최소한 pj개의 운석 샘플을 가지고 있어야 하며, 유성우 예보 기간 안에 운석 샘플을 다 채우지 못 할 경우 NIE(폴란드어로 NO를 의미)를 출력한다.
예제 입력 1
3 5 1 3 2 1 3 10 5 7 3 4 2 4 1 3 1 3 5 2
예제 출력 1
3 NIE 1
출처
Olympiad > Polish Olympiad in Informatics > POI 2010/2011 > Stage 3 5번
- 문제를 번역한 사람: plzrun
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호