Problem: claw (2018 finals)

Oh boy, Sid's family has taken him to Pizza Planet today! Pizza Planet is a
fun family restaurant with lots of arcade games, but the highlight for Sid is
Space Crane, a crane game with cool toy prizes. He'd love to win some to add
to his collection!

Looking at Space Crane from the front, it can be represented as a 2D plane. At
the top, there's a horizontal crane track, a line segment running from (0,
**M**) to (1,000,000, **M**). There's a claw attached to this track by an
extendible wire. The claw is initially located at coordinates (0, **M**) and
may be moved anywhere within the inclusive range of x-coordinates [0,
1,000,000] and the inclusive range of y-coordinates [0, **M**]. At all points
in time, the connecting wire runs vertically upwards from the claw's position
to the track. That is, when the claw is at some point (**x**, **y**), the wire
forms a line segment from (**x**, **y**) to (**x**, **M**).

Space Crane works differently than most crane games — rather than using the
claw to directly pick up prizes, the player's objective is to navigate the
claw to a series of targets. There are **N** targets, all with distinct
x-coordinates, with the _i_th target at coordinates (**Xi**, **Yi**). If Sid
manages to move the claw to touch the **N** targets in order from 1 to **N**,
and then return the claw to its original position at (0, **M**), he'll win a
prize! Targets are not collected along the way (they're only touched by the
claw), meaning that all **N** targets will remain in place for the duration of
the game.

The claw may never be anywhere directly underneath a target (at the same
x-coordinate but with a strictly smaller y-coordinate), as it would interfere
with the crane's wire. However, the claw may occupy exactly the same position
as a target, including passing directly through targets which Sid is not
currently trying to touch.

Before the game starts, Sid is given an opportunity to adjust each of the
**N** targets. There are two possible choices for each target: it may either
be left in its original position, or its y-coordinate may be increased by
exactly 1 unit. These adjustments may only be performed in advance, and the
targets must then all remain in their chosen positions for the duration of the
game.

Completing the game normally isn't much of a challenge for Sid, but he's heard
a rumour that Space Crane awards double prizes if completed as efficiently as
possible! The game measures efficiency based on how much the claw's wire
expands and contracts. As such, Sid would like to adjust the targets and then
move the claw around such that the total amount of vertical movement (changes
in y-coordinate) performed by the claw is minimized. Note that the claw's
horizontal movement (changes in x-coordinate) is ignored. Help Sid determine
the minimum total amount of vertical claw movement which might be required!

### Input

Input begins with an integer **T**, the number of times Sid plays Space Crane.
For each game, there is first a line containing the space-separated integers
**N** and **M**. Then **N** lines follow, the _i_th of which contains the
space-separated integers **Xi** and **Yi**.

### Output

For the _i_th game, output a line containing "Case #_i_: " followed by the the
minimum total amount of vertical claw movement, in units.

### Constraints

1 ≤ **T** ≤ 100  
1 ≤ **N** ≤ 1,000,000  
3 ≤ **M** ≤ 1,000,000  
0 ≤ **Xi** ≤ 1,000,000  
1 ≤ **Yi** ≤ **M** \- 2  

### Explanation of Sample

In the first case, the single target's height should be increased from 1 to 2.
Then, aside from moving right and left by 1,000,000 units, the crane will need
to move downwards by 8 units to reach the target and upwards by 8 units to
return to its original position, for a total of 16 units of vertical movement.

In the second case, if the targets are all left at their original heights, 10
units of vertical movement will be required. If their heights are all
increased by 1, 8 units will be required. However, if just the first two
targets are raised, then only 6 units will be required, which is the minimum
achievable amount.



Sample input:
5
1 10
1000000 1
3 5
1 1
3 1
2 2
5 10
30 5
20 4
40 4
10 3
50 3
8 100
44 51
8 37
65 71
36 62
92 29
74 71
11 62
93 85
25 50
75 29
94 41
68 41
72 31
35 9
8 25
23 34
32 20
95 24
51 34
67 24
88 19
46 24
57 31
78 24
58 41
36 43
31 24
22 34
80 47
25 24
43 43
59 41
47 41
87 22


Sample output:
Case #1: 16
Case #2: 6
Case #3: 14
Case #4: 260
Case #5: 568



Code: // The Claw
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define LIM 2100000

PR P[LIM],R[LIM],S[LIM];
vector<int> YP[LIM];
vector<PR> YR[LIM];
int sz;
int tree[LIM],lazy[LIM];

void Prop(int i)
{
	tree[i]+=lazy[i];
		if (i<sz)
		{
			lazy[i<<1]+=lazy[i];
			lazy[(i<<1)+1]+=lazy[i];
		}
	lazy[i]=0;
}

void Update(int i,int r1,int r2,int a,int b,int v)
{
	Prop(i);
		if ((a<=r1) && (r2<=b))
		{
			lazy[i]+=v;
			Prop(i);
			return;
		}
	int c=i<<1,m=(r1+r2)>>1;
		if (a<=m)
			Update(c,r1,m,a,b,v);
		if (b>m)
			Update(c+1,m+1,r2,a,b,v);
	Prop(c),Prop(c+1);
	tree[i]=max(tree[c],tree[c+1]);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N,M,K;
	int i,j,k,s,y,a,b,p,d;
	LL ans;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// init
				Fox(i,LIM)
					YP[i].clear(),YR[i].clear();
			// input
			Read(N),Read(M);
			ans=M;
				Fox(i,N)
				{
					Read(P[i].x),Read(P[i].y);
					ans-=P[i].y;
					YP[P[i].y].pb(P[i].x);
						if (i)
							R[i-1]=mp(max(P[i-1].x,P[i].x),min(P[i-1].x,P[i].x));
				}
			// associate intervals with their max contained heights
			sort(P,P+N);
			sort(R,R+N-1);
			j=s=0;
				Fox(i,N-1)
				{
					a=R[i].y,b=R[i].x;
					// maintain convex hull of max heights so far
						while ((j<N) && (P[j].x<=b))
						{
								while ((s) && (S[s-1].y<=P[j].y))
									s--;
							S[s++]=P[j++];
						}
					// binary search for max height no earlier than the start of this interval
					k=lower_bound(S,S+s,mp(a,0))-S;
					ans+=(y=S[k].y)+1;
					YR[y].pb(R[i]);
				}
			// process set of targets at each height
				Fox(i,LIM)
					if (K=Sz(YP[i]))
					{
						// sort targets/intervals at this height
						sort(All(YP[i]));
						sort(All(YR[i]));
						// segment-tree-assisted DP
							for(sz=1;sz<K+1;sz<<=1);
						memset(tree,0,sizeof(int)*sz*2);
						memset(lazy,0,sizeof(int)*sz*2);
						k=0,d=-1;
							Fox(j,K+1)
							{
								// update prior DP values for intervals ending at this target
								p=j==K ? INF : YP[i][j];
									while ((k<Sz(YR[i])) && (YR[i][k].x<p))
									{
										a=lower_bound(All(YP[i]),YR[i][k++].y)-YP[i].begin();
										Update(1,0,sz-1,0,a,1);
									}
								// compute DP value
								d=max(d+1,tree[1]);
								Update(1,0,sz-1,j,j,d);
							}
						ans-=d;
					}
			// output
			printf("Case #%d: %lld\n",t,ans*2);
		}
	return(0);
}