USACO Gold 2016 Open - Splitting the Field

Official Analysis

1#include <bits/stdc++.h>
2using namespace std; 
3
4const int MX = 5e4; 
5int n, x[MX], y[MX], ar[MX];
6
7bool cmp (int a, int b) { 
8    if (x[a] == x[b]) return y[a] < y[b];
9    return x[a] < x[b];
10}

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$.

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using 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