USACO Gold 2016 Open - Splitting the Field

Official Analysis

#include <bits/stdc++.h>
using namespace std; 

const int MX = 5e4; 
int n, x[MX], y[MX], ar[MX];

bool cmp (int a, int b) { 
	if (x[a] == x[b]) return y[a] < y[b];
	return x[a] < x[b];
}

Alternative

From the analysis:

Note that it is also possible to dispense with the binary search trees entirely and just keep running mins and maxes in $y$.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double; 
using str = string; // yay python!

using pi = pair<int,int>;
using pl = pair<ll,ll>;

Note - Weak Test Data

The above codes give different outputs on the following test case:

17
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
2 3
2 4
3 2
3 3
3 4
4 2
4 3
4 4