시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 1033 | 290 | 180 | 22.814% |
눈꽃 나라엔 하루 종일 눈이 온다. 눈이 아주 많이 온다. 내린 눈은 계속해서 쌓이고 녹는다.
눈꽃 나라의 기상 캐스터 택희는 눈에 관해서만 일기예보를 한다. 지진이 나도, 태풍이 와도 택희는 항상 아래와 같은 예보만 한다.
현재 적설량이 Limm 이상 Rimm 이하인 지역은 A, B, C, ... , X 이상 K개의 지역입니다.
택희는 항상 위와 같은 방식으로 예보를 했지만, 눈꽃 나라가 행정구역 개편을 하며 나뉜 지역 수가 무려 N개가 되는 바람에 K개의 지역을 일일히 언급하는 것은 너무 힘들게 되었다. 그래서 택희는 그냥 적설량이 Limm 이상 Rimm 이하인 지역의 수 K만 세기로 마음먹었다. 하지만 이 방식으로는 각 지역에 대한 정보를 전혀 알 수 없었기 때문에, 현재 T번째로 눈이 많이 온 지역에 눈이 얼마나 쌓였는지도 언급하기로 하였다. 하지만 지역이 많이 늘어났다 보니 만만치 않은 작업이었다. 따라서 택희는 각 지역의 적설량을 체크하는 자동화 프로그램을 작성해보려 한다.
택희의 프로그램은 아래와 같은 네 가지 작업을 처리할 수 있어야 한다.
4번 작업을 좀 더 정확히 말하면, 만일 같은 값이 있다면 중복해서 모두 센다. 예를 들어 다섯 지역에 쌓인 눈이 (3, 1, 2, 1, 2) 일 때, 4번 작업에서 T가 각각 1, 2, 3, 4, 5일 때의 답은 3, 2, 2, 1, 1이 된다.
기상예보는 신속 정확이 생명이므로, 위와 같은 연산을 아주 빨리 할 수 있는 프로그램이 필요하다. 택희는 열심히 노력했지만, 어떤 프로그램도 위와 같은 연산을 빠르게 처리하지 못했다. 택희를 위해 여러분이 더 빠른 프로그램을 하나 만들어주도록 하자.
첫째 줄에 눈꽃 나라의 지역 수 N, 프로그램이 처리해야 할 명령의 수 M이 주어진다. (1 ≤ N, M ≤ 105)
둘째 줄에 N개의 정수로 현재 각 지역에 쌓인 눈의 양 Si가 주어진다. (0 ≤ Si ≤ 109)
셋째 줄부터 M개의 줄에 걸쳐 다음 네 가지 형태 중 하나의 명령이 주어진다.
2번 명령으로 인해 어떤 지역의 적설량이 음수가 되는 경우는 없다.
3, 4번 명령이 주어질 때마다 하나의 정수로 답을 출력한다.
5 7 0 0 1 0 0 1 2 2 3 1 2 1 5 5 3 2 5 4 3 2 5 5 3 2 5
2 2 1 1
University > 연세대학교 > 2017 연세대학교 컴퓨터과학과 프로그래밍 경진대회 J번