Horizontal Walls
National Olympiad — National round (2019 season)
Submission name: wall.cpp
Problem summary
Start at cell (X,1). Horizontal walls cover upward edges at distinct heights; crossing a wall costs V instead of one second. Other adjacent steps cost one. Find the shortest travel time to each exit.
Input
X; N M; N rows sX fX Y V; M exit coordinates.
Output
One minimum travel time per exit, in input order.
Constraints
N,M ≤ 200,000; coordinates and V < 10^9; 2 ≤ sX ≤ fX; 2 ≤ exit x; wall heights are distinct.
Worked example
An independently prepared example for this explanation.
Input
4 1 2 2 4 3 2 3 3 3 4
Output
3 5
Solution analysis
- A shortest route can be made vertically nondecreasing: a downward excursion begins and ends on the same row, and replacing it by horizontal travel cannot increase its cost. Sweep walls and exits by increasing height. Subtract y−1 from all distances, leaving a horizontal-cost profile F(x), initially |x−X|.
- For wall [l,r] with density V, first add V−1 inside its interval. Then cap the result by the two routes around its endpoints: F(l−1)+x−(l−1) and F(r+1)+(r+1)−x. Outside the wall the profile is unchanged. Before and after each completed wall update the profile is 1-Lipschitz, so F(x)−x is nonincreasing and F(x)+x is nondecreasing.
- Compress wall endpoints, the two outside cells, start, and exits. A lazy segment tree supports interval addition, assignment to a line of slope ±1, and maxima of F−x and F+x. Each cap replaces a prefix or suffix of the wall interval; a tree descent finds its boundary. In example 1 the exit below the wall costs 3; the higher exit can cross density 2 and costs 5. With density 100, going around the right endpoint costs 6 instead.
Why it works
Removing a downward excursion is valid because its horizontal displacement costs at least the direct horizontal walk, while removing vertical motion removes only positive costs. At a wall an optimal monotone path either crosses within the interval, at extra cost V−1, or enters above it from an outside endpoint. The 1-Lipschitz property makes crossing elsewhere inside no better than crossing directly at x. Thus the three-way minimum is exact. The difference from the left cone is nonincreasing and from the right cone nondecreasing, proving that the capped sets are a prefix and suffix. Tree operations apply this recurrence exactly at every coordinate that can be queried or serve as a future endpoint.
Watch out. Exits at height Y are answered before the wall at height Y. Add V−1, not V, because ordinary upward seconds are restored separately. Include l−1 and r+1 in compression; use 64-bit distances.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
using Integer=long long;
struct Node{
Integer minus=0,plus=0,add=0,intercept=0;
int slope=0;
};
struct Tree{
vector<Integer>x;
vector<Node>nodes;
Tree(vector<Integer>coordinates,Integer start):x(coordinates),nodes(4*x.size()){
build(1,0,int(x.size())-1,start);
}
void pull(int v){
nodes[v].minus=max(nodes[v*2].minus,nodes[v*2+1].minus);
nodes[v].plus=max(nodes[v*2].plus,nodes[v*2+1].plus);
}
void assign(int v,int l,int r,int slope,Integer intercept){
nodes[v].slope=slope;
nodes[v].intercept=intercept;
nodes[v].add=0;
nodes[v].minus=(slope-1)*x[l]+intercept;
nodes[v].plus=(slope+1)*x[r]+intercept;
}
void increase(int v,Integer value){
nodes[v].minus+=value;
nodes[v].plus+=value;
nodes[v].add+=value;
}
void push(int v,int l,int r){
int m=(l+r)/2;
if(nodes[v].slope!=0){
assign(v*2,l,m,nodes[v].slope,nodes[v].intercept);
assign(v*2+1,m+1,r,nodes[v].slope,nodes[v].intercept);
nodes[v].slope=0;
}
if(nodes[v].add!=0){
increase(v*2,nodes[v].add);
increase(v*2+1,nodes[v].add);
nodes[v].add=0;
}
}
void build(int v,int l,int r,Integer start){
if(x[r]<=start){
assign(v,l,r,-1,start);
}
else if(x[l]>=start){
assign(v,l,r,1,-start);
}
else{
int m=(l+r)/2;
build(v*2,l,m,start);
build(v*2+1,m+1,r,start);
pull(v);
}
}
void update(int v,int l,int r,int a,int b,int slope,Integer value){
if(a>r||b<l||a>b){
return;
}
if(a<=l&&r<=b){
if(slope==0){
increase(v,value);
}
else{
assign(v,l,r,slope,value);
}
return;
}
push(v,l,r);
int m=(l+r)/2;
update(v*2,l,m,a,b,slope,value);
update(v*2+1,m+1,r,a,b,slope,value);
pull(v);
}
Integer get(int v,int l,int r,int at){
if(l==r){
return nodes[v].plus-x[l];
}
push(v,l,r);
int m=(l+r)/2;
return at<=m?get(v*2,l,m,at):get(v*2+1,m+1,r,at);
}
int boundary(int v,int l,int r,int a,int b,Integer threshold,bool fromRight){
Integer maximum=fromRight?nodes[v].minus:nodes[v].plus;
if(a>r||b<l||maximum<=threshold){
return -1;
}
if(l==r){
return l;
}
push(v,l,r);
int m=(l+r)/2;
int found;
if(fromRight){
found=boundary(v*2+1,m+1,r,a,b,threshold,fromRight);
return found!=-1?found:boundary(v*2,l,m,a,b,threshold,fromRight);
}
found=boundary(v*2,l,m,a,b,threshold,fromRight);
return found!=-1?found:boundary(v*2+1,m+1,r,a,b,threshold,fromRight);
}
};
struct Event{
Integer y,left,right,cost;
int id;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
Integer start;
int n,m;
cin>>start>>n>>m;
vector<Event>events;
vector<Integer>coordinates={1,start};
for(int i=0;i<n;i++){
Integer l,r,y,cost;
cin>>l>>r>>y>>cost;
events.push_back({y,l,r,cost,-1});
coordinates.insert(coordinates.end(),{l-1,l,r,r+1});
}
for(int i=0;i<m;i++){
Integer x,y;
cin>>x>>y;
events.push_back({y,x,x,0,i});
coordinates.push_back(x);
}
sort(coordinates.begin(),coordinates.end());
coordinates.erase(unique(coordinates.begin(),coordinates.end()),coordinates.end());
sort(events.begin(),events.end(),[](const Event&a,const Event&b){
return a.y!=b.y?a.y<b.y:a.id>b.id;
});
Tree tree(coordinates,start);
int last=int(coordinates.size())-1;
auto index=[&](Integer value){
return int(lower_bound(coordinates.begin(),coordinates.end(),value)-coordinates.begin());
};
vector<Integer>answer(m);
for(const Event&event:events){
int l=index(event.left),r=index(event.right);
if(event.id!=-1){
answer[event.id]=tree.get(1,0,last,l)+event.y-1;
continue;
}
Integer leftCone=tree.get(1,0,last,l-1)-coordinates[l-1];
Integer rightCone=tree.get(1,0,last,r+1)+coordinates[r+1];
// Remove the unavoidable one second per upward move from the profile.
tree.update(1,0,last,l,r,0,event.cost-1);
int end=tree.boundary(1,0,last,l,r,leftCone,true);
if(end!=-1){
tree.update(1,0,last,l,end,1,leftCone);
}
int begin=tree.boundary(1,0,last,l,r,rightCone,false);
if(begin!=-1){
tree.update(1,0,last,begin,r,-1,rightCone);
}
}
for(Integer value:answer){
cout<<value<<'\n';
}
}