#PU1258. USACO 2022 December Contest, Gold — Problem 2. Mountains
USACO 2022 December Contest, Gold — Problem 2. Mountains
USACO 2022 December Contest, Gold — Problem 2. Mountains
题目描述
Note: the time limit for this problem is 5s, 2.5 times the default. The memory limit is twice the default. There are () evenly spaced mountains in a row on the edge of Farmer John's farm. These can be expressed as an array of heights . For a mountain , you can see another mountain if there are no mountains strictly higher than the line of sight connecting the tops of mountain and . Formally, for two mountains , they can see each other if there is no such that and is above the line segment connecting and . There are () updates where the height of one mountain increases. Find the total number of unordered pairs of mountains that see each other after each update.
输入格式
Line contains . Line contains heights (for each , ). Line contains . Lines to contain , (, ) where is the index of the mountain and is the amount the height increases by. It is guaranteed that the new height of the mountain is at most .
输出格式
lines, with the total number of unordered pairs of mountains that see each other after each update.
数据范围
Tests 2-5 satisfy . Tests 6-11 satisfy . Tests 12-21 have no additional constraints. Problem credits: Joe Li and Larry Xing
样例
样例 1
5
2 4 3 1 5
3
4 3
1 3
3 2
7
10
7
Initially, 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$.