USACO 2020 Silver Problem 2

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

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<pair<int, int>> a(n);
    for (auto& it : a) cin >> it.first >> it.second;
    sort(a.begin(), a.end());

    typedef long long ll;
    ll nl[n][n][2], ng[n][n][2]; //precalculate the number of y-coordinates less than one of the endpoints, and the number of y-coordinates greater than one of the endpoints
    for (int i = 0; i < n; i++){
        int cl=0, cg=0;
        for (int j = i; j < n; j++){
            if (a[j].second < a[i].second) cl++;
            if (a[j].second > a[i].second) cg++;
            nl[i][j][0] = cl;
            ng[i][j][0] = cg;
        }
    }
    for (int j = 0; j < n; j++){
        int cl=0, cg=0;
        for (int i = j; i >= 0; i--){
            if (a[i].second < a[j].second) cl++;
            if (a[i].second > a[j].second) cg++;
            nl[i][j][1] = cl;
            ng[i][j][1] = cg;
        }
    }
    ll ans=n+1; //empty subset counts -> initially start with n+1 for all rectangles that have single points
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            if (a[i].second <= a[j].second){
                ans += (1+nl[i][j][0])*(1+ng[i][j][1]);
            } else {
                ans += (1+nl[i][j][1])*(1+ng[i][j][0]);
            }
        }
    }
    //number outside the bounds are possible, the rest are fixed
    cout << ans << '\n';
}