Proficient.
Put your skills to the test.

Problem summary

A relief has integer heights, begins by rising, and has specified alternating valleys and peaks, including both endpoints. Adjacent heights differ. Some heights are fixed. First minimize the global height range, then minimize the sum of the heights at all specified extrema.

Constraints

2 ≤ T ≤ 300000; 1 ≤ W ≤ min(N,300000); 1=a[0]<...<a[T−1]=N≤300000; fixed heights have absolute value ≤10^9. The data describe a feasible relief.

Worked example

An independently prepared example for this explanation.

7
1 2 4 7 9 11 14
1
6 5

3 29

Solution analysis

1. Between consecutive extrema the heights must change strictly in one direction, so a segment of horizontal length d needs at least d units of vertical difference. A known point at height h and distance d from a peak forces that peak to be at least h+d; relative to a valley it forces that valley to be at most h−d.
2. Collect these bounds from known points in each monotone segment. Known extrema have equal lower and upper bounds. Let L be the greatest lower bound, U the smallest upper bound, and D the longest horizontal segment. The minimum range is H=max(L−U,D): every bound and segment requires this much, and placing all free valleys at the lower window endpoint and free peaks at the upper endpoint realizes it.
3. To minimize the sum, select the lowest feasible height window [L−H,L]. Put every free valley at its bottom; fixed valleys stay fixed. Then set each free peak to the largest of its original lower bound and the heights required above its neighboring valleys. For the sample, the optimal window is [3,6]; extrema heights are 3,5,3,6,3,6,3, with total 29.

Why it works

Bounds induced by known points ensure enough integer levels on each side of each known height. A segment without internal known points requires only its endpoint difference to be at least its horizontal length. Therefore H is both necessary and sufficient. Any feasible range-H window has upper endpoint at least L, so its lower endpoint is at least L−H. Lowering free valleys to that value never hurts a lower-bound requirement on peaks. Once valleys are fixed, the smallest feasible peak is exactly the maximum of its local requirements. These independent choices minimize every free extremum and hence the sum.

Watch out. Extrema alternate starting with a valley. The peak height is the maximum of lower bounds, not the minimum. Unknown heights and the sum may be negative; use signed 64-bit arithmetic.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: Between consecutive extrema the heights must change strictly in one direction, so a
// segment of horizontal length d needs at least d units of vertical difference.
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    vector<int>position(t);
    for(int&value:position){
        cin>>value;
    }
    int n=position.back();
    vector<bool>known(n+1,false);
    vector<long long>fixed(n+1,0);
    int w;
    cin>>w;
    while(w--){
        int index;
        long long height;
        cin>>index>>height;
        known[index]=true;
        fixed[index]=height;
    }
    const long long INF=4000000000000000000LL;
    vector<long long>lower(t,-INF),upper(t,INF),height(t);
    for(int i=0;i<t;++i){
        if(known[position[i]]){
            lower[i]=upper[i]=fixed[position[i]];
        }
    }
    long long longest=0;
    for(int i=0;i+1<t;++i){
        longest=max(longest,1LL*position[i+1]-position[i]);
        for(int point=position[i];point<=position[i+1];++point){
            if(!known[point]){
                continue;
            }
            if(i%2==0){
                upper[i]=min(upper[i],fixed[point]-(point-position[i]));
                lower[i+1]=max(lower[i+1],fixed[point]+position[i+1]-point);
            }
            else{
                lower[i]=max(lower[i],fixed[point]+point-position[i]);
                upper[i+1]=min(upper[i+1],fixed[point]-(position[i+1]-point));
            }
        }
    }
    long long greatestLower=*max_element(lower.begin(),lower.end());
    long long smallestUpper=*min_element(upper.begin(),upper.end());
    long long range=max(longest,greatestLower-smallestUpper);
    long long bottom=greatestLower-range;
    for(int i=0;i<t;i+=2){
        height[i]=known[position[i]]?fixed[position[i]]:bottom;
    }
    for(int i=1;i<t;i+=2){
        if(known[position[i]]){
            height[i]=fixed[position[i]];
            continue;
        }
        height[i]=max(lower[i],height[i-1]+position[i]-position[i-1]);
        if(i+1<t){
            height[i]=max(height[i],height[i+1]+position[i+1]-position[i]);
        }
    }
    long long sum=0;
    for(long long value:height){
        sum+=value;
    }
    cout<<range<<' '<<sum<<'\n';
}