USACO Open Contest 2016 Gold - Splitting the Field

Official Editorial: http://www.usaco.org/current/data/sol_split_gold_open16.html

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

int N;
ll ans = 0;
vpi v;

void tri() {
    sort(all(v));
    vpi lef(N), rig(N);
    auto comb = [](pi a, int b) -> pi { return {min(a.f,b),max(a.s,b)}; };
    lef[0] = {v[0].s,v[0].s};
    FOR(i,1,N) lef[i] = comb(lef[i-1],v[i].s);

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