레이팅 미적용*참고: 이 문제의 시간 제한은 기본값의 2.5배인 5초이다. 메모리 제한은 기본값의 두 배이다.*
농부 존의 농장 가장자리에는 \(N\)개(\(1 \leq N \leq 2000\))의 산이 일정한 간격으로 한 줄로 서 있다. 이는 높이 배열 \(h_1,h_2,\dots,h_N\)으로 나타낼 수 있다. 산 \(i\)에서 산 \(j\)의 꼭대기를 잇는 시선보다 순전히 높은 산이 없으면 산 \(i\)에서 산 \(j\)를 볼 수 있다. 형식적으로, 두 산 \(i < j\)에 대해 \(i < k < j\)이면서 \((k, h_k)\)가 \((i, h_i)\)와 \((j, h_j)\)를 잇는 선분보다 위에 있는 \(k\)가 존재하지 않으면 두 산은 서로를 볼 수 있다. 한 산의 높이가 증가하는 \(Q\)개(\(1 \leq Q \leq 2000\))의 갱신이 주어진다. 각 갱신 후, 서로를 볼 수 있는 산의 순서 없는 쌍의 총 개수를 구하시오.
출제: Joe Li and Larry Xing
배점
- 테스트 2-5는 \(N, Q\le 100\)을 만족한다.
- 테스트 6-11은 \(Q \leq 10\)을 만족한다.
- 테스트 12-21은 추가 제약이 없다.
출제: Joe Li and Larry Xing
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 높이 \(h_1,h_2,\dots,h_N\)이 주어진다(각 \(i\)에 대해 \(0 \leq h_i \leq 10^9\)).
셋째 줄에 \(Q\)가 주어진다.
넷째 줄부터 \(3+Q\)번째 줄까지 \(x\), \(y\) (\(1 \leq x \leq N\), \(1 \leq y\))가 주어지며, \(x\)는 산의 인덱스이고 \(y\)는 높이가 증가하는 양이다. 산의 새 높이는 \(10^9\) 이하임이 보장된다.
\(Q\)개의 줄에 걸쳐, 각 갱신 후 서로를 볼 수 있는 산의 순서 없는 쌍의 총 개수를 출력한다.
5
2 4 3 1 5
3
4 3
1 3
3 27
10
7Initially, the following pairs of mountains can see each other: \((1, 2)\),
\((2, 3)\), \((2, 5)\), \((3, 4)\), \((3, 5)\), \((4, 5)\), a total of \(6\).
After the first update, mountain \(4\) has a height of \(4\), which doesn't block
any visibility but does make it so that \(4\) can now see \(2\), making the new
answer \(7\).
After the second update, mountain \(1\) has a height of \(5\), which doesn't block
any visibility but does make it so that \(1\) can now see \(3\), \(4\), and \(5\),
making the new answer \(10\).
After the third update, mountain \(3\) has a height of \(5\), which blocks mountain
\(1\) from seeing mountain \(4\), blocks mountain \(2\) from seeing mountains \(4\) and
\(5\), and doesn't allow itself to see any more mountains since it can already see
all of them, making the new answer
\(7\).
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > December > Gold