読者です 読者をやめる 読者になる 読者になる

AtCoder ARC 073 Ball Coloring

細かくコメント書いてみた。

/*
2個の配列u,vを値(u[i], v[i])でソートする。
*/
template<class S, class T>
void psort(vector<S> &u, vector<T> &v, bool isGreater);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vll X(N), Y(N);
    rep(i, N) {
        cin >> X[i] >> Y[i];
        // 簡単のためX[i]<=Y[i]とする
        if (X[i] > Y[i])swap(X[i], Y[i]);
    }
    /*
    最大値と最小値が同じ色になるかどうかで場合分けする
    とりあえず、最大値と最小値が異なる色になる場合について
    最大値を含む方は、大きい数を貪欲に
    最小値を含む方は、小さい数を貪欲に
    選ぶ。
    なお、最小値と最大値がそれぞれちょうど1個ずつであってかつ同じ袋に入っている場合は
    同じ色にできない。
    */
    ll rma = 0, rmi = INT_MAX, bma = 0, bmi = INT_MAX;
    rep(i, N) {
        smax(rma, X[i]);
        smin(rmi, X[i]);
        smax(bma, Y[i]);
        smin(bmi, Y[i]);
    }
    // 解(暫定)
    ll ans = (rma - rmi)*(bma - bmi);

    /*
    (X[i],Y[i])でソートする
    m, Mが同じ色に含まれる。
    (m, M)=(rmi, bma)とする。こちらは、入力全体の最小値と最大値を含んでいる。
    他方の最小、最大は
    (z, Z)とする。
    zを昇順で固定する。ただし、Zはできるだけ小さい方がいい。
    zより小さい値はどんどん取り除いていく尺取。要するに、(z, Z)に含まれる値hは
    h>=zかつできるだけ小さいのが好ましい。
    しゃくとりみたいな感じでやる。
    */
    psort(X, Y);
    // 最小値、最大値の(m, M)内の数
    int nm = 0, nM = 0;
    ll red = bma - rmi;
    // <値, id>
    set<pair<ll, int> > st, ts;
    rep(i, N) {
        // 袋stには(z, Z)が含まれている。
        // (全体)-stには(m, M)が含まれていてほしい
        st.insert(mp(X[i], i));
        // すべてのボールの値をzの候補として昇順で見たいのでtsに突っ込んでいく。ソートされる。
        ts.insert(mp(X[i], i));
        ts.insert(mp(Y[i], i));
        if (Y[i] == rmi)nm++;
        if (Y[i] == bma)nM++;
    }

    /*
    (z, Z)を含む色について
    値aを取り除いてbを挿入
    */
    auto f = [&](ll a, ll b, int k) {
        if (X[k] != Y[k] && st.count(mp(a, k))) {
            st.erase(mp(a, k));
            st.insert(mp(b, k));
            if (a == rmi)nm++;
            if (a == bma)nM++;
            if (b == rmi)nm--;
            if (b == bma)nM--;
        }
    };

    [&] {
        each(p, ts) {
            /*
            zを最小値として固定
            */
            int k = p.second;
            ll z = p.first, w = X[k] ^ Y[k] ^ z;
            
            f(w, z, k);
            while (sz(st) && st.begin()->first < z) {
                ll u = st.begin()->first, v;
                int l = st.begin()->second;
                v = u ^ X[l] ^ Y[l];
                // すべての値をz以上にすることは不可能である。
                if (v < z) {
                    return;
                }
                f(u, v, l);
            }
            /*
            他方にm,Mが含まれている場合のみ計算
            */
            if (nm > 0 && nM > 0) {
                smin(ans, red*(st.rbegin()->first - st.begin()->first));
            }
        }
    }();
    cout << ans << endl;
}