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]