Daeshin High School and Queries

$4 \times N$ 크기의 배열을 만들어 각 반의 불쾌함을 직접 저장한다.

1번 쿼리에서는 공사가 발생한 위치와 상하좌우의 다섯 위치를 확인한다. 건물 안에 있는 위치만 불쾌함을 $1$ 증가시킨다. 확인하는 위치의 수가 일정하므로 한 번의 갱신은 $O(1)$이다.

2번 쿼리에서는 해당 층의 반을 $1$번부터 $N$번까지 순서대로 확인한다. 지금까지 확인한 최댓값보다 불쾌함이 엄격히 큰 경우에만 답을 갱신하면, 동점일 때 번호가 가장 작은 반이 자동으로 선택된다.

모든 쿼리를 처리한 뒤에는 $1$층부터 $4$층까지, 각 층에서는 $1$반부터 $N$반까지 순서대로 확인한다. 마찬가지로 최댓값보다 엄격히 큰 경우에만 답을 갱신하면 문제에서 요구한 우선순위를 만족한다.

시간 복잡도는 $O(QN)$이고, 공간 복잡도는 $O(N)$이다.

Solution written by GPT5.6