| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 6 초 | 2048 MB | 3 | 2 | 2 | 100.000% |
$0$번 관측탑부터 $N-1$번 관측탑까지 $N$개의 관측탑이 순서대로 설치되어 있다. $0 \le i \le N-1$에 대해 $i$번 관측탑의 높이는 $H[i]$이다. 또한 각 관측탑은 관측 점수 $S[i]$를 가지며, 초기에는 모든 관측 점수는 $0$이다.
$0 \le i < j \le N-1$를 만족하는 $i, j$에 대해, $i$번 관측탑에서 $j$번 관측탑이 관측 가능하다는 것은 모든 $i \le k \le j-1$에 대해 $H[k] < H[j]$임을 의미한다. $j \le i$인 관측탑들은 관측 가능하지 않음에 유의하라.
어떤 관측탑에서 관측을 진행하면, 해당 관측탑에서 관측 가능한 모든 관측탑의 관측 점수가 $1$ 증가한다.
이제 $Q$개의 이벤트가 일어난다. 각 이벤트는 다음 세 가지 종류 중 하나이다.
관측 이벤트는 배열 $[I]$로, 측정 이벤트는 배열 $[L, R]$로, 지각 변동 이벤트는 배열 $[L, R, V]$로 표현할 수 있다. 이벤트의 종류마다 배열의 크기가 다르기에 배열의 크기를 기준으로 어떤 이벤트인지 구분할 수 있음에 유의하라.
이벤트들은 $0$번 이벤트부터 $Q-1$번 이벤트까지 순서대로 일어나며, $i$번 이벤트는 $E[i]$이다.
총 측정 이벤트의 개수를 $K$라 하자. 각 측정 이벤트를 일어난 순서대로 $0$번 측정 이벤트부터 $K-1$번 측정 이벤트라고 하자. 모든 측정 이벤트의 결과값, 즉 $0$번 측정 이벤트부터 $K-1$번 측정 이벤트의 결과값을 모두 구해야 한다.
다음 함수를 구현해야 한다.
vector<long long> tower_events(vector<int> H, vector<vector<int>> E)
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 17 | $N, Q \le 150\,000$. 모든 측정 이벤트에서 $L = 0$, $R = N-1$이다. |
| 2 | 6 | $N, Q \le 150\,000$. 지각 변동 이벤트가 일어나지 않는다. |
| 3 | 12 | $N, Q \le 150\,000$. |
| 4 | 19 | 모든 관측 이벤트에서 $I = 0$이다. 모든 지각 변동 이벤트에서 $L = R$이다. 지각 변동 이벤트는 최대 $30\,000$번 일어난다. |
| 5 | 21 | 모든 측정 이벤트에서 $L = R$이다. 모든 지각 변동 이벤트에서 $L = R$이며 $V \ge 0$이다. |
| 6 | 25 | 추가적인 제약조건이 없다. |
예제 1
다음 호출을 생각해보자:
tower_events([1, 2, 3, 4, 5], [[0], [1, 3], [1, 2, 1], [1], [0, 4]])
따라서 함수는 $[3,6]$을 반환해야 한다.
예제 2
다음 호출을 생각해보자:
tower_events([7, 7, 9, 5, 8, 10, 2, 9, 2, 2], [[1], [6, 8, 6], [1], [1, 9], [3], [8], [2, 4], [5], [1, 1, 7], [1], [0, 9]])
함수는 $[5, 3, 10]$을 반환해야 한다.
샘플 그레이더의 입력 형식은 다음과 같다.
샘플 그레이더는 다음 형식으로 답을 출력한다:
Olympiad > 국제정보올림피아드 대표학생 선발고사 > 2026 > 2차 선발고사 4번
C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)