USACO 2020 January Contest, Gold Problem 3. Springboards

USACO 2020 January Contest, Gold Problem 3. Springboards

Bessie is in a 2D grid where walking is permitted only in directions parallel to one of the coordinate axes. She starts at the point (0,0)(0,0) and wishes to reach (N,N)(N,N) (1≤N≤1091≤N≤109). To help her out, there are PP (1≤P≤1051≤P≤105) springboards on the grid. Each springboard is at a fixed point (x1,y1)(x1,y1) and if Bessie uses it, she will land at a point (x2,y2)(x2,y2).

Bessie is a progress-oriented cow, so she only permits herself to walk up or right, never left nor down. Likewise, each springboard is configured to never go left nor down. What is the minimum distance Bessie needs to walk?

 

 

 

 

SAMPLE INPUT:

3 2
0 1 0 2
1 2 2 3

SAMPLE OUTPUT:

3

Bessie's best path is:

• Bessie walks from (0,0) to (0,1) (1 unit).
• Bessie springs to (0,2).
• Bessie walks from (0,2) to (1,2) (1 unit).
• Bessie springs to (2,3).
• Bessie walks from (2,3) to (3,3) (1 unit).

The total walking length of Bessie's path is 3 units.

 

Problem credits: Pedro Paredes

<h3> USACO 2020 January Contest, Gold Problem 3. Springboards 题解(翰林国际教育提供，仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Benjamin Qi)

For each springboard i,i, let ans[i]ans[i] denote the minimum distance needed to walk to the start point of springboard ii. If Bessie walks directly to this springboard, then the distance is x1[i]+y1[i].x1[i]+y1[i]. Otherwise, Bessie last took some springboard jj before walking to springboard i,i, giving a distance of ans[j]+x1[i]+y1[i]−x2[j]−y2[j],ans[j]+x1[i]+y1[i]−x2[j]−y2[j], where both x2[j]≤x1[i]x2[j]≤x1[i] and y2[j]≤y1[i]y2[j]≤y1[i] must be satisfied.

Sort all springboard start and endpoints by xx. Then for each x1[i]x1[i] in increasing order we need to compute the minimum possible value of ans[j]−x2[j]−y2[j]ans[j]−x2[j]−y2[j] over all jj such that x2[j]≤x1[i]x2[j]≤x1[i] and y2[j]≤y1[i].y2[j]≤y1[i]. Our approach requires some data structure DD that stores pairs and supports the following operations.

For each pair in increasing lexicographical order:

• If we're currently considering the end point of a springboard ii, insert (y2[i],ans[i]−x2[i]−y2[i])(y2[i],ans[i]−x2[i]−y2[i]) into DD.
• If we're currently considering the start point of a springboard ii, query the pair (y2[j],ans[j]−x2[j]−y2[j])∈D(y2[j],ans[j]−x2[j]−y2[j])∈D with maximum second element that satisfies y2[j]≤y1[i]y2[j]≤y1[i]. Then update ans[i]ans[i] accordingly.

One candidate for DD is a segment tree that supports point updates and range minimum queries. A simpler approach is to use a map.

 

• When the point (x2[j],y2[j])(x2[j],y2[j]) is reached, consider the pair pj=(y2[j],ans[j]−x2[j]−y2[j]).pj=(y2[j],ans[j]−x2[j]−y2[j]).
  • If there already exists a pair pk∈Dpk∈D such that y2[k]≤y2[j]y2[k]≤y2[j] and ans[k]−x2[k]−y2[k]≤ans[j]−x2[j]−y2[j],ans[k]−x2[k]−y2[k]≤ans[j]−x2[j]−y2[j], then there is never any reason to use springboard jj over springboard k,k, so DD remains unchanged.
  • Otherwise, while there exists kk such that pk∈Dpk∈D y2[k]≥y2[j]y2[k]≥y2[j] and ans[k]−x2[k]−y2[k]≥ans[j]−x2[j]−y2[j],ans[k]−x2[k]−y2[k]≥ans[j]−x2[j]−y2[j], remove pkpk from DD. Then insert pjpj into DD.
• When querying for y1[i],y1[i], it suffices to consider only the pair in DD with maximum first element such that its first element is at most y1[i].y1[i]. This works because pairs with higher first element in DD have lower second element.

These operations run in O(logn)O(log⁡n) time amortized.

 

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

const int MX = 1e5+5;

int N,P;
map<int,int> m;
int ans[MX];
 
void ins(int y, int v) {
	auto it = prev(m.upper_bound(y));
	if (it->s <= v) return;
	it ++;
	while (it != end(m) && it->s > v) m.erase(it++);
	m[y] = v;
}
 
int main() {
	setIO("boards");
	cin >> N >> P; m[0] = 0;
	vector<pair<pair<int,int>,pair<int,int>>> ev;
	for (int i = 0; i < P; ++i) {
		pair<int,int> a,b; 
		cin >> a.f >> a.s >> b.f >> b.s;
		ev.push_back({a,{i,-1}}); // start point
		ev.push_back({b,{i,1}}); // end point
	}
	sort(begin(ev),end(ev));
	for (auto& t: ev) {
		if (t.s.s == -1) {
			ans[t.s.f] = t.f.f+t.f.s+prev(m.upper_bound(t.f.s))->s;
		} else {
			ins(t.f.s,ans[t.s.f]-t.f.f-t.f.s);
		}
	}
	cout << m.rbegin()->s+2*N;
}

[/hide]