Real problems.
Your next challenge.

Problem summary

Place K stations on a row of hills, allowing repeated positions. A station sees a hill if no intermediate hill is at least as tall as the station. Travel time is the sum along the row. Minimize the worst time to a visible station, or report impossibility.

Source clarification. The worked example prints the valid optimal placement 2 6 rather than reproducing the source’s printed placement. The implementation and geometric validator use the stated visibility rule, including blocking by equal-height intermediate hills.

Constraints

1 ≤ K ≤ N ≤ 500000; heights and travel times are between1 and10^9.

Worked example

The second original sample input, with an independently verified optimal placement; any valid optimal placement is accepted.

7 2
1 2 1 3 2 2 1
1 1 1 1 1 1

2
2 6

Solution analysis

1. For a fixed candidate time X, every station covers a contiguous interval of hills. Monotonic stacks find its nearest hills of height at least its own on both sides. Those blocking hills themselves are visible, but hills beyond them are not. Intersect this visibility interval with the travel-distance interval [position−X,position+X]. Two pointers find all distance intervals in linear time.
2. Now cover hill indices1..N using as few of these intervals as possible. At the leftmost uncovered hill, choose an interval that starts no later and reaches farthest right. Store the best right endpoint for each left endpoint, then prefix maxima; this is counting-sort style processing, avoiding a comparison sort during each check.
3. A feasible X uses at most K intervals; extra stations may duplicate any chosen location. Binary-search X between0 and the end-to-end travel time. If even that upper bound needs more than K stations, visibility makes the request impossible. In the sample, stations2 and6 cover all hills within time2.

Why it works

For a fixed X, the visibility and distance tests exactly characterize a station’s coverage interval. Among intervals covering the first uncovered hill, replacing a chosen interval by the farthest-reaching one cannot leave any later hill less covered; induction proves the greedy cover uses the minimum count. Increasing X only enlarges intervals, so feasibility is monotone and binary search finds the optimum.

Watch out. The first blocking hill remains visible: do not exclude its endpoint. Travel distances and binary-search bounds need long long. The answer must include a valid placement, not only the optimum time. Duplicate placements are explicitly allowed.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    vector<int>height(n);
    for(int&h:height){
        cin>>h;
    }
    vector<long long>position(n,0);
    for(int i=1;i<n;i++){
        long long time;
        cin>>time;
        position[i]=position[i-1]+time;
    }
    vector<int>visibleLeft(n),visibleRight(n),stack;
    for(int i=0;i<n;i++){
        while(!stack.empty()&&height[stack.back()]<height[i]){
            stack.pop_back();
        }
        visibleLeft[i]=stack.empty()?0:stack.back();
        stack.push_back(i);
    }
    stack.clear();
    for(int i=n-1;i>=0;i--){
        while(!stack.empty()&&height[stack.back()]<height[i]){
            stack.pop_back();
        }
        visibleRight[i]=stack.empty()?n-1:stack.back();
        stack.push_back(i);
    }
    vector<int>reach(n),station(n),chosen;
    auto feasible=[&](long long limit,bool remember){
        fill(reach.begin(),reach.end(),-1);
        int left=0;
        int right=0;
        for(int i=0;i<n;i++){
            while(position[i]-position[left]>limit){
                left++;
            }
            while(right+1<n&&position[right+1]-position[i]<=limit){
                right++;
            }
            int from=max(left,visibleLeft[i]);
            int to=min(right,visibleRight[i]);
            if(to>reach[from]){
                reach[from]=to;
                station[from]=i;
            }
        }
        // Prefix maxima choose the farthest interval starting no later than x.
        for(int i=1;i<n;i++){
            if(reach[i-1]>reach[i]){
                reach[i]=reach[i-1];
                station[i]=station[i-1];
            }
        }
        if(remember){
            chosen.clear();
        }
        int used=0;
        int uncovered=0;
        while(uncovered<n){
            if(reach[uncovered]<uncovered||++used>k){
                return false;
            }
            if(remember){
                chosen.push_back(station[uncovered]+1);
            }
            uncovered=reach[uncovered]+1;
        }
        return true;
    };
    long long low=0;
    long long high=position.back();
    if(!feasible(high,false)){
        cout<<-1<<'\n';
        return 0;
    }
    while(low<high){
        long long middle=low+(high-low)/2;
        if(feasible(middle,false)){
            high=middle;
        }
        else{
            low=middle+1;
        }
    }
    feasible(low,true);
    while(static_cast<int>(chosen.size())<k){
        chosen.push_back(chosen.front());
    }
    cout<<low<<'\n';
    for(int i=0;i<k;i++){
        if(i>0){
            cout<<' ';
        }
        cout<<chosen[i];
    }
    cout<<'\n';
}