MLE 0pts求条

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

struct pt {
    int x, y;
} p[500001];

bool cmp1(const pt& p1, const pt& p2) {
    return p1.x < p2.x;
}

bool cmp2(const pt& p1, const pt& p2) {
    return p1.y < p2.y;
}

int n;

int fxb[500001][30], fxs[500001][30], fyb[500001][30], fys[500001][30];

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].x >> p[i].y;
    }
    memset(fxs, 0x3f, sizeof (fxs));
    memset(fys, 0x3f, sizeof (fys));
    sort(p + 1, p + n + 1, cmp1);
    int maxnx = p[n].x, minnx = p[1].x;
    for (int i = 1; i <= n; i++) {
        fxb[i][0] = fxs[i][0] = p[i].x;
        fyb[i][0] = fys[i][0] = p[i].y;
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << (j - 1)) <= n; i++) {
            fxb[i][j] = max(fxb[i][j - 1], fxb[i + (1 << (j - 1))][j - 1]);
            fyb[i][j] = max(fyb[i][j - 1], fyb[i + (1 << (j - 1))][j - 1]);
            fxs[i][j] = min(fxs[i][j - 1], fxs[i + (1 << (j - 1))][j - 1]);
            fys[i][j] = min(fys[i][j - 1], fys[i + (1 << (j - 1))][j - 1]);
        }
    }
    int ans = INT_MAX;
    for (int i = 1; i < n; i++) {
        int l = __lg(i);
        int maxx = max(fxb[1][l], fxb[i - (1 << l) + 1][l]);
        int maxy = max(fyb[1][l], fyb[i - (1 << l) + 1][l]);
        int minx = min(fxs[1][l], fxs[i - (1 << l) + 1][l]);
        int miny = min(fys[1][l], fys[i - (1 << l) + 1][l]);
        int l2 = __lg(n - i);
        int maxx2 = max(fxb[i + 1][l2], fxb[n - (1 << l2) + 1][l2]);
        int maxy2 = max(fyb[i + 1][l2], fyb[n - (1 << l2) + 1][l2]);
        int minx2 = min(fxs[i + 1][l2], fxs[n - (1 << l2) + 1][l2]);
        int miny2 = min(fys[i + 1][l2], fys[n - (1 << l2) + 1][l2]);
        ans = min(ans, (maxx - minx) * (maxy - miny) + (maxx2 - minx2) * (maxy2 - miny2));
    }
    sort(p + 1, p + n + 1, cmp2);
    int maxny = p[n].y, minny = p[1].y;
    for (int i = 1; i <= n; i++) {
        fxb[i][0] = fxs[i][0] = p[i].x;
        fyb[i][0] = fys[i][0] = p[i].y;
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << (j - 1)) <= n; i++) {
            fxb[i][j] = max(fxb[i][j - 1], fxb[i + (1 << (j - 1))][j - 1]);
            fyb[i][j] = max(fyb[i][j - 1], fyb[i + (1 << (j - 1))][j - 1]);
            fxs[i][j] = min(fxs[i][j - 1], fxs[i + (1 << (j - 1))][j - 1]);
            fys[i][j] = min(fys[i][j - 1], fys[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 1; i < n; i++) {
        int l = __lg(i);
        int maxx = max(fxb[1][l], fxb[i - (1 << l) + 1][l]);
        int maxy = max(fyb[1][l], fyb[i - (1 << l) + 1][l]);
        int minx = min(fxs[1][l], fxs[i - (1 << l) + 1][l]);
        int miny = min(fys[1][l], fys[i - (1 << l) + 1][l]);
        int l2 = __lg(n - i);
        int maxx2 = max(fxb[i + 1][l2], fxb[n - (1 << l2) + 1][l2]);
        int maxy2 = max(fyb[i + 1][l2], fyb[n - (1 << l2) + 1][l2]);
        int minx2 = min(fxs[i + 1][l2], fxs[n - (1 << l2) + 1][l2]);
        int miny2 = min(fys[i + 1][l2], fys[n - (1 << l2) + 1][l2]);
        ans = min(ans, (maxx - minx) * (maxy - miny) + (maxx2 - minx2) * (maxy2 - miny2));
    }
    cout << (maxnx - minnx) * (maxny - minny) - ans;
    return 0;
}