Jim and the Skyscrapers#11720

Jim and the Skyscrapers (Editorial)

Imagine that we are building "walls" out of blocks of the same height.

A pair $(i, j)$ forms a "corridor" if there is no taller block between these walls. To solve the problem, we'll use a monotone stack. The stack stores pairs $(v a l u e, co u n t)$ (value, count):

$v a l u e$ — the height of the wall (the value $h [i]$ ).
$co u n t$ — the number of consecutive elements of this height that have already appeared and can form pairs with future elements of the same height.

That is:

For each "block of identical numbers", we remember only two parameters: the number itself and how many times it has appeared consecutively so far.
When a new element appears, we can immediately determine how many pairs it forms: this number is exactly $co u n t$ for the element at the top of the stack.

For example, let the current number be $a = 5$ a = 5, and suppose it has already appeared $3$ times (that is, the current occurrence of $a = 5$ a = 5 is the fourth one). Assume that between all these occurrences of a there are only smaller elements. Then the number of new index pairs $(i, j)$ , where $j$ is the current index and the condition $h_{i} = h_{j} = a$ h_i = h_j = a holds, will be $3$ .

When processing the next number $h_{i}$ h_i:

If the number at the top of the stack is less than $h_{i}$ h_i, remove it from the stack.
If the number at the top of the stack is equal to $h_{i}$ h_i and it has appeared previously $x$ times, increase the target count of index pairs by $x$ and update the number of occurrences of $h_{i}$ h_i to $x + 1$ x + 1.
If the stack is empty or the number at the top of the stack is greater than $h_{i}$ h_i, push the pair $(h_{i}, 1)$ (h_i, 1) onto the stack. This means that the current value $h_{i}$ h_i appears for the first time (it may have appeared earlier in the input sequence but was removed from the stack due to a larger element).

Example

Consider the first test case.

Algorithm implementation

Read the input data.

scanf("%d", &n);
vector<int> v(n);
for (i = 0; i < n; ++i)
  scanf("%d", &v[i]);

Store the number of found index pairs in the variable $r es$ .

res = 0;

Declare a stack of pairs.

stack<pair<int, int>> st;

Process all the numbers of the array sequentially.

for (i = 0; i < v.size(); i++)
{

While the number at the top of the stack is less than $v [i]$ , remove it from the stack.

  while (!st.empty() && st.top().first < v[i])
    st.pop();

If the number at the top of the stack is equal to $v [i]$ and it has appeared previously $x$ times (the value $x$ is stored in $s t . t o p () . seco n d$ st.top().second), increase the answer $r es$ by $x$ . Then update the number of occurrences of $v [i]$ to $x + 1$ x + 1.

  if (!st.empty() && v[i] == st.top().first)
  {
    res += st.top().second;
    st.top().second += 1;
  }
  else

If $v [i]$ appears for the first time, push the pair $(v [i], 1)$ (v[i], 1) onto the stack.

    st.push({ v[i], 1 });
}

Print the answer.

printf("%lld\n", res);