Problem: strolls (2017 finals)

A certain forest has **N** trees growing in it, and there just so happens to
be a Fox living at the top of each one! The trees are numbered from 1 to
**N**, and their bases are all arranged in a straight line on the ground, with
1 metre between the bases of each pair of adjacent trees _i_ and _i_ \+ 1.
Each tree _i_ is **Hi** metres tall.

The Foxen are all good friends with one another, and frequently like to go out
for strolls to visit each other's homes. Rather than jumping directly between
the trees, they prefer to always keep their paws firmly planted on some
surface, such as tree trunks or the ground. As such, the shortest possible
trip from the top of tree _i_ to the top of another tree _j_ requires climbing
down tree _i_ to the ground, walking along the ground to the base of tree _j_,
and then climbing up to its top, resulting in a total distance of **Hi** \+
|_j_ \- _i_| + **Hj** metres traveled.

However, the Foxen aren't terribly satisfied with how long their trips
currently take. Given the frequency of their strolls, they've decided to
invest in reducing their travel distance by constructing some bridges between
the tree trunks. They're only interested in building metre-long, horizontal
bridges. Each bridge may be constructed to connect any pair of adjacent trees
_i_ and _i_ \+ 1, and it may be placed at any height above the ground, as long
as it touches both of those tree trunks (in other words, its height must be no
larger than the minimum of **Hi** and **Hi+1**). Multiple bridges may be
constructed at different heights between any given pair of adjacent trees.
Once bridges are installed, the Foxen will be willing to walk across them,
potentially saving them the time of descending all the way to the ground
during their strolls.

There are **N** * **(N - 1)** / 2 different pairs of Foxen _i_ and _j_ who
might want to meet up, requiring a trip to be taken from the top of tree _i_
to the top of tree _j_ (or vice versa). The Foxen's top priority is minimizing
the sum of the **N** * **(N - 1)** / 2 pairwise shortest distances of strolls
which would be required for these visits to take place. Please help them
determine the minimum possible value of this sum, assuming that they construct
as many bridges as it takes. That being said, they don't want to spend all day
constructing bridges either... as such, they're also interested in the minimum
number of bridges which they can construct to achieve that minimum possible
sum of pairwise distances.

### Input

Input begins with an integer **T**, the number of forests. For each forest,
there are two lines. The first line contains the integer **N**. The second
line contains **N** space-separated integers, the _i_th of which is the
integer **Hi**.

### Output

For the _i_th forest, print a line containing "Case #**i**: " followed by two
integers: the minimum possible sum of pairwise shortest distances after any
number of bridges are built (in metres), and the minimum number of bridges
required to achieve that minimum sum.

### Constraints

1 ≤ **T** ≤ 30  
2 ≤ **N** ≤ 500,000  
1 ≤ **Hi** ≤ 10,000,000  
The sum of **N** values across all **T** cases does not exceed 6,000,000.

### Explanation of Sample

In the first case, the Foxen's optimal strategy is to construct one bridge
between the first 2 trees at a height of 20m, and another bridge between the
last 2 trees at a height of 10m. With this configuration, the shortest path
between the first 2 trees' tops is 11m long, as is the shortest path for the
last 2 trees. The shortest path between the first tree's top and the last
tree's top is 22m long. The resulting sum of pairwise shortest distances is
then 44m, which is the minimum possible sum.



Sample input:
5
3
30 20 10
5
1 2 3 2 1
7
8 3 7 11 8 8 6
7
6279148 9485166 9832201 1 8916058 9059232 7182836
15
172 472 972 472 493 736 487 384 918 856 124 975 376 846 173


Sample output:
Case #1: 44 2
Case #2: 30 6
Case #3: 158 9
Case #4: 213877494 8
Case #5: 67828 26



Code: // Hacker Cup 2017
// Final Round
// Fox Strolls
// Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 500000

int main()
{
	// vars
	int T,t;
	int N;
	int i,j,a,b,h;
	LL ans1,ans2;
	static int H[LIM];
	static PR P[LIM];
	stack<PR> ST;
	set<int> S;
	set<int>::iterator I;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N);
				Fox(i,N)
				{
					Read(H[i]);
					P[i]=mp(H[i],i);
				}
			// PART 1: sum of distances
			ans1=0;
			// get base sum assuming no bridges
				Fox(i,N)
					ans1+=H[i];
			ans1*=N-1;
				Fox1(i,N-1)
					ans1+=(LL)i*(N-i);
			// process trees bottom-to-top
			sort(P,P+N);
			S.clear();
			S.insert(-1);
			S.insert(N);
				Fox(i,N)
				{
					h=P[i].x;
					j=P[i].y;
					// find interval of paths having this as their shortest tree
					I=S.lower_bound(j);
					b=*I - 1;
					I--;
					a=*I + 1;
					// subtract total distance saved by bridges
					ans1-=(LL)h*2*((LL)(j-a)*(b-j) + (b-a));
					// insert this tree
					S.insert(j);
				}
			// PART 2: number of bridges
			ans2=0;
			// process trees left-to-right
				while (!ST.empty())
					ST.pop();
			ST.push(mp(0,0));
				Fox1(i,N-1)
					if (H[i]>=H[i-1])
					{
						// at least as high as envelope's highest point, so build single bridge backwards
							if (ST.top().x==H[i-1])
								ST.pop();
						ST.push(mp(H[i-1],i));
						ans2++;
					}
					else
					{
						// clip off higher parts of envelope
						j=i-1;
							while (ST.top().x>H[i])
								j=ST.top().y,ST.pop();
						// build row of bridges back across, and update envelope
							if (!ST.top().x)
								ans2+=i-j;
							else
							{
								ans2+=i-ST.top().y;
								h=ST.top().x,ST.pop();
									if (H[i]!=h)
										ST.push(mp(h,j));
							}
						ST.push(mp(H[i],i));
					}
			// output
			printf("Case #%d: %lld %lld\n",t,ans1,ans2);
		}
	return(0);
}