**Analysis: Cow Crossings by Brian Dean**

This problem can be approached several different ways.

One idea that perhaps comes to mind initially but is not quite correct is to sort the cows on A and then sort again on B, and treat a cow as safe if it ends up in the same position in both orderings. However, this unfortunately does not work, due to cases like this:

3 1 3 2 2 3 1

The key observation we should make to solve this problem is that a cow is safe if all the cows before her in the A ordering are also before her in B, and if all the cows after her in A are also after her in B. We can test this efficiently by sorting the cows on A and then scanning through the ordering, keeping a running maximum of the B value of each cow as we go. When we reach a particular cow (a,b), we check if the max B we have seen so far is smaller than b -- this means that all the cows before (a,b) in the A ordering are also before this cow in the B ordering. We then need to do the same thing in reverse: scan backwards through the A ordering while keeping a running minimum of the B values; when we encounter a cow (a,b), we test if the min B we have seen so far is larger than b, as this ensure that all the cows after (a,b) in the A ordering are also after this cow in the B ordering.

Here is Jonathan Paulson's solution written in Java:

```
import java.util.*;
import java.io.*;
import java.awt.Point;
import static java.lang.Math.*;
public class crossings {
public static int i(String s) { return Integer.parseInt(s); }
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new FileReader("crossings.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new
FileWriter("crossings.out")));
int n = i(in.readLine());
int[][] P = new int[n][2];
for(int i=0; i<n; i++) {
String[] arr = in.readLine().split(" ");
P[i] = new int[]{i(arr[0]), i(arr[1])};
}
Arrays.sort(P, new Comparator<int[]>() {
public int compare(int[] A, int[] B) {
return A[0]-B[0];
}
});
int[] maxl = new int[n];
maxl[0] = P[0][1];
for(int i=1; i<n; i++)
maxl[i] = Math.max(maxl[i-1], P[i][1]);
int[] minr = new int[n];
minr[n-1] = P[n-1][1];
for(int i=n-2; i>=0; i--)
minr[i] = Math.min(minr[i+1], P[i][1]);
int safe = 0;
for(int i=0; i<n; i++) {
boolean ok = true;
if(i!=0 && maxl[i-1] > P[i][1]) ok = false;
if(i!=n-1 && minr[i+1] < P[i][1]) ok = false;
if(ok) safe++;
}
out.println(safe);
out.flush();
}
}
```

Here is a solution from Travis Hance written in C++:

```
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define NMAX 100000
struct Crossing {
int x1, x2;
int x2index;
};
Crossing crossings[NMAX];
inline bool cmp1(Crossing a, Crossing b) {
return a.x1 < b.x1;
}
inline bool cmp2(Crossing a, Crossing b) {
return a.x2 < b.x2;
}
int main() {
freopen("crossings.in","r",stdin);
freopen("crossings.out","w",stdout);
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &crossings[i].x1);
scanf("%d", &crossings[i].x2);
}
sort(crossings, crossings + n, cmp2);
for (int i = 0; i < n; i++) {
crossings[i].x2index = i;
}
sort(crossings, crossings + n, cmp1);
int answer = 0;
int maxX2indexSeen = -1;
for (int i = 0; i < n; i++) {
if (crossings[i].x2index == i && maxX2indexSeen == i-1) {
answer++;
}
maxX2indexSeen = max(maxX2indexSeen, crossings[i].x2index);
}
printf("%d\n", answer);
}
```