(Analysis by Nick Wu)

After we do a bit of processing of the problem statement, we reword it as follows: we are given a set of lattice points. We can start at any lattice point and we can move to another lattice point if and only if that lattice point has $x$ and $y$ coordinates that strictly exceed that of the point we are currently at. We wish to compute the maximum number of lattice points we can visit.

This immediately motivates a dynamic programming approach where we process the points from left to right, keeping track of the maximum number of points we can visit given the point that we end up at. This approach is $O(N^2)$.

To optimize this, we leverage some structure of the dynamic programming algorithm. In particular, note that for a given point, we're performing a query for the maximum over all processed points that are below it. If we process points along the same $x$-coordinate in decreasing order of $y$-coordinate, we can maintain a max-range tree on the maximal number of points that we can visit ending at a given $y$-coordinate. Instead of needing to consider $O(N)$ preceding points, we can query and update in $O(\log N)$ for an $O(N \log N)$ algorithm.

import java.io.*;
import java.util.*;
public class nocross {

public static void main(String[] args) throws IOException {
PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("nocross.out")));
int[] l = new int[n];
for(int i = 0; i < n; i++) {
}
int[] locOf = new int[n];
for(int i = 0; i < n; i++) {
}
RangeTree dp = new RangeTree(n+1);
for(int i = 0; i < n; i++) {
ArrayList<Integer> indices = new ArrayList<Integer>();
for(int a = Math.max(0, l[i] - 4); a < Math.min(n, l[i] + 5); a++) {
}
Collections.sort(indices);
for(int a = indices.size()-1; a >= 0; a--) {
dp.update(indices.get(a)+1, dp.query(0, indices.get(a)) + 1);
}
}
pw.println(dp.query(0, n));
pw.close();
}

static class RangeTree {
int[] leaf;
int size;
public RangeTree(int n) {
leaf = new int[4*n];
size = n;
}
public void update(int index, int val) {
update(1, 0, size-1, index, val);
}
private void update(int index, int l, int r, int i, int v) {
if(l == r) {
leaf[index] = v;
}
else {
int m = (l+r)/2;
if(i <= m) {
update(2*index, l, m, i, v);
}
else {
update(2*index+1, m+1, r, i, v);
}
leaf[index] = Math.max(leaf[2*index], leaf[2*index+1]);
}
}
public int query(int l, int r) {
return query(1, 0, size-1, l, r);
}
public int query(int index, int l, int r, int lhs, int rhs) {
if(l >= lhs && r <= rhs) {
return leaf[index];
}
int ret = 0;
int m = (l+r)/2;
if(m >= lhs) {
ret = Math.max(ret, query(2*index, l, m, lhs, rhs));
}
if(m+1 <= rhs) {
ret = Math.max(ret, query(2*index+1, m+1, r, lhs, rhs));
}
return ret;
}
}

}