Mountains
골드 II의견: 0
*Note: the time limit for this problem is 5s, 2.5 times the default. The
memory limit is twice the default.*
There are \(N\) (\(1 \leq N \leq 2000\)) evenly spaced mountains in a row on the edge of
Farmer John's farm. These can be expressed as an array of heights
\(h_1,h_2,\dots,h_N\). For a mountain \(i\), you can see another mountain \(j\) if
there are no mountains strictly higher than the line of sight connecting the
tops of mountain \(j\) and \(i\). Formally, for two mountains \(i < j\), they can see
each other if there is no \(k\) such that \(i < k < j\) and \((k, h_k)\) is above the
line segment connecting \((i, h_i)\) and \((j, h_j)\). There are \(Q\)
(\(1 \leq Q \leq 2000\)) updates where the height of one mountain increases. Find
the total number of unordered pairs of mountains that see each other after each
update.
Problem credits: Joe Li and Larry Xing
SCORING
- Tests 2-5 satisfy \(N, Q\le 100\).
- Tests 6-11 satisfy \(Q \leq 10\).
- Tests 12-21 have no additional constraints.
Problem credits: Joe Li and Larry Xing
Line \(1\) contains \(N\).
Line \(2\) contains \(N\) heights \(h_1,h_2,\dots,h_N\) (for each \(i\),
\(0 \leq h_i \leq 10^9\)).
Line \(3\) contains \(Q\).
Lines \(4\) to \(3+Q\) contain \(x\), \(y\) (\(1 \leq x \leq N\), \(1 \leq y\)) where \(x\) is
the index of the mountain and \(y\) is the amount the height increases by. It is
guaranteed that the new height of the mountain is at most \(10^9\).
\(Q\) lines, with the total number of unordered pairs of mountains that see each
other after each update.
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
평가 및 의견
Mountains
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Mountains