Problem: personal (2018 finals)

Phineas is the proud owner of an enormous new fish tank! Looking at the fish
tank from the side, it can be represented as an infinite 2D plane. Phineas has
installed **N** vertical dividers into the tank, the _i_th of which is a line
segment connecting points (**Xi**, **Ai**) and (**Xi**, **Bi**). No two
dividers overlap at any point (including at their endpoints).

Unfortunately, Phineas's fish tank is lacking in fish, but he'll soon rectify
that! He's going to place one or more fish into the tank, with each one
initially occupying any point of his choice (each coordinate may be non-
integral and arbitrarily small or large). No fish's location may overlap with
any of the dividers (including their endpoints), but multiple fish may be
placed at the same coordinates.

After the fish have been placed, each one may swim left and right freely
(continuously decreasing or increasing its x-coordinate), as long as it never
touches a divider (including its endpoints). Fish do not block one another
from swimming, so multiple fish are able to occupy the same coordinates.
However, no fish is able to change its y-coordinate.

At any given moment, each fish feels that its personal space is violated if
any other fish is currently at the same x-coordinate as it (either at its
current y-coordinate, or arbitrarily far above or below it). As such, if two
fish ever occupy the same x-coordinate as one another, they both become
unhappy.

Phineas suspects that someone's planning on stealing one of his dividers soon
after he places fish into the tank!

And he wants to ensure that none of his fish have any chance of becoming
unhappy!

But he still wants to have as many fish as possible!

As such, he'd like to determine the maximum number of fish which he can place
into the tank such that, no matter which single one of the **N** dividers is
subsequently removed, and no matter how the fish then decide to swim around,
none of the fish can ever become unhappy.

### Input

Input begins with an integer **T**, the number of fish tanks. For each fish
tank, there is first a line containing the single integer **N**. Then, **N**
lines follow, the _i_th of which contains the 3 space-separated integers
**Xi**, **Ai**, and **Bi**.

### Output

For the _i_th fish tank, output a line containing "Case #_i_: " followed by
the maximum number of fish which Phineas can place into the tank with no risk
of unhappiness.

### Constraints

1 ≤ **T** ≤ 90  
1 ≤ **N** ≤ 500,000  
0 ≤ **Xi** ≤ 1,000,000,000  
0 ≤ **Ai** < **Bi** ≤ 1,000,000,000  

### Explanation of Sample

In the first case, Phineas could, for example, place a fish at coordinates (5,
5). If he placed another fish anywhere else in the tank (for example at
coordinates (-1, 2)), then if the single divider were removed, both fish would
be able to swim freely and might come to occupy the same x-coordinate as one
another.

In the second case, Phineas can place one fish at coordinates (-5, 5) and
another at coordinates (15, 5).

In the third case, no matter where Phineas might place two fish in the tank,
at least one choice of removed divider would result in them potentially
becoming unhappy.



Sample input:
5
1
0 0 10
2
0 0 5
10 5 10
2
0 0 5
10 6 10
8
10 22 26
9 11 14
22 24 29
9 21 30
5 8 18
21 9 14
16 18 24
16 3 12
30
42 18 53
1 20 45
29 9 22
15 6 52
32 28 40
46 43 71
37 42 47
3 4 47
33 22 39
19 46 94
27 22 61
20 13 31
50 36 81
4 12 35
34 24 39
12 4 23
48 45 58
8 38 48
24 42 72
17 36 77
43 39 46
41 43 58
49 47 53
30 21 22
7 2 46
35 5 12
9 45 85
38 39 58
16 40 49
5 31 59


Sample output:
Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 3
Case #5: 12



Code: // Personal Space
// 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 8000001

int K1,K2;
pair<PR,int> E1[LIM];
pair<PR,PR> E2[LIM];
int dyn[LIM];
set<int> S1;
set<PR> S2;
set<int>::iterator I1;
set<PR>::iterator I2,J2;

void AddRect(int x1,int y1,int x2,int y2)
{
		if ((x2<0) || (y1>INF))
			return;
	int i=K2+1;
	E2[K2++]=mp(mp(y1,1),mp(x1,i));
	E2[K2++]=mp(mp(y2,0),mp(x2,i));
}

void AddRects(int x)
{
	int i;
	int X[7];
	I1=S1.lower_bound(x);
		Fox(i,3)
			I1--;
		Fox(i,7)
			X[i]=*I1,I1++;
		Fox(i,4)
			AddRect(X[i],X[i+1],X[i+2],X[i+3]);
}

int Query(int x)
{
	I2=S2.lower_bound(mp(x+1,0));
	I2--;
	return(I2->y);
}

void Update(int x,int v)
{
	I2=S2.lower_bound(mp(x+1,0));
	I2--;
		if (v<=I2->y)
			return;
		if (I2->x<x)
			I2++;
		while ((I2!=S2.end()) && (v>=I2->y))
		{
			J2=I2,I2++;
			S2.erase(J2);
		}
	S2.insert(mp(x,v));
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int N;
	int i,j,k,x,a,b,ans;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N);
			K1=0;
				Fox(i,N)
				{
					Read(x),Read(a),Read(b);
					E1[K1++]=mp(mp(a,x),1);
					E1[K1++]=mp(mp(b+1,x),-1);
				}
			// bottom-up line sweep to generate all possible fish placement "rectangles"
			sort(E1,E1+K1);
			S1.clear();
				Fox1(i,4)
					S1.insert(-i),S1.insert(INF+i);
			K2=0;
				Fox(i,K1)
				{
					j=i;
						while ((j+1<K1) && (E1[j+1].x.x==E1[i].x.x))
							j++;
						FoxI(k,i,j)
							if (E1[k].y>0)
								S1.insert(E1[k].x.y);
							else
								S1.erase(E1[k].x.y);
						FoxI(k,i,j)
							AddRects(E1[k].x.y);
					i=j;
				}
			// bottom-up line sweep DP on rectangles
			sort(E2,E2+K2);
			S2.clear();
			S2.insert(mp(-INF,0));
			ans=0;
				Fox(i,K2)
				{
					x=E2[i].y.x,j=E2[i].y.y;
						if (E2[i].x.y)
							Max(ans,dyn[j]=Query(x)+1);
						else
							Update(x,dyn[j]);
				}
			// output
			printf("Case #%d: %d\n",t,ans);
		}
	return(0);
}