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; }