22033번 - 가로등 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 103 | 6 | 4 | 7.843% |
문제
일직선으로 된 도로를 따라 $N$개의 가로등이 세워져 있다. $i$번째 가로등의 초기 높이는 $A_i$이다$(1 \le i \le N)$. 가로등을 이용하여 전기줄을 설치하려고 한다.
$i$번 가로등과 $j( \gt i)$번 가로등 사이에 전기줄을 걸기 위해서는 다음 두 조건을 모두 만족해야 한다.
- $A_i = A_j$ (두 가로등의 높이가 같다.)
- 모든 $i < k < j$에 대하여, $A_k < A_i$이다. (두 가로등 사이에 있는 모든 가로등의 높이는 두 가로등보다 낮다.)
일부 가로등은 관리자의 판단에 따라 높이가 조정되며, 높이가 조정된 가로등으로 인해 전기줄을 걸 수 있는 상황이 변경된다.
"$x$번째 가로등의 높이를 $h$로 변경"하는 높이 조정 작업은 총 $Q$번 행해진다. 가로등 높이 변경이 이루어질 때마다, 높이 조정 후 전기줄을 걸 수 있는 가로등 쌍의 개수를 계산하는 프로그램을 작성하고자 한다.
입력
첫째 줄에 두 정수 $N$, $Q$가 주어진다. $2 \le N \le 100\,000, 1 \le Q \le 250\,000$
다음 줄에는 $N$개의 정수 $A_1, A_2, \ldots, A_N$가 주어진다. ($1 \le A_i \le 10^9$)
다음 $Q$개의 줄에는 두 정수 $x$, $h$가 주어지며, $A_x = h$를 나타낸다. ($1 \le x \le N, 1 \le h \le 10^9$) 조정 직전의 $x$번째 가로등의 높이는 $h$와 다름이 보장된다.
출력
첫째 줄에 초기에 설치된 가로등에 걸 수 있는 전기줄의 개수를 출력한다.
다음 $Q$개의 줄에는 높이 조정 작업 각각에 대해, 높이 조정 후 가로등에 걸 수 있는 전기줄의 개수를 출력한다.
서브태스크 1 (5점)
- $N \le 50$
- $Q \le 100$
서브태스크 2 (8점)
- $N \le 10\,000$
- $Q \le 25\,000$
서브태스크 3 (11점)
- $A_i \le 10, h \le 10$
서브태스크 4 (7점)
- 모든 높이 조정 작업은 가로등의 높이를 감소시킨다.
서브태스크 5 (15점)
- 한 번 높이가 증가한 가로등은 이후 높이가 감소하지 않는다.
- 한 번 높이가 감소한 가로등은 이후 높이가 증가하지 않는다.
서브태스크 6 (12점)
- $Q \le 8\,000$
서브태스크 7 (16점)
- 한 번이라도 높이가 변하는 가로등은 총 $8\,000$개 이하이다.
서브태스크 8 (21점)
- $N \le 40\,000$
- $Q \le 100\,000$
서브태스크 9 (55점)
- 추가적인 제약 조건이 없다.
예제 입력 1
6 2 4 2 2 2 4 6 4 6 6 4
예제 출력 1
3 2 2
출처
Camp > Petrozavodsk Programming Camp > Winter 2022 > Day 2: Grand Prix of Daejeon I번
Olympiad > 국제정보올림피아드 대표학생 선발고사 > 2021 > 2차 선발고사 4번
Contest > Open Cup > 2021/2022 Season > Stage 11: Grand Prix of Daejeon I번
- 문제를 만든 사람: yclock
채점 및 기타 정보
- 예제는 채점하지 않는다.
- 이 문제의 채점 우선 순위는 2이다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호