[AGC040] B - Two Contests

[Q] https://atcoder.jp/contests/agc040/tasks/agc040_b
[A] https://youtu.be/qIzuNgDV6O8?t=493

解説Vを見て、ようやく抜いた。
使うのは2本のセグ木。LのRangeMaxと、RのRangeMin。

(2022/12/16)  セグ木使わない。最大値のメモだけでいける。
https://atcoder.jp/contests/agc040/submissions/37290599

1. maxLとminRを調べる

a) maxLのid == minRのid はとても簡単。[maxL, minR]の区間は必ず全員正解になる。
1日に1番長い辺をとって、
2日にその他全部をとればいい。
ans = longest + (minR - maxL)
これはどんな入力ケースでも解答候補になるので、最初に求めておく。

b) maxLのid と minRのid が違うとき。

LでもRでも、どっちでもいいんだけど、Lに着目しようと思う。
maxLのときのRをdefRとする。[maxL, defR] をグループAにとりあえず採用。

Rで降順sortし、Rが大きい値からみていく。O(N)。

c) defR < R なら、グループＡに採用しちゃう。
[maxL, defR] を必ず満たすので、グループＡのスコアは変わらない。

d) defR >= R のとき。グループAに採用すると[maxL, R] が正解範囲になる。
残グループＢのスコアは、
[ＬのRangeMax, ＲのRangeMin]なので、O(logN)で求められるので、
ans = グループA + グループＢで最大値の更新をすればいい。

実装

int main() {
 cincout();

 ll N;
 cin >> N;
 vector<pll> L(N);
 vector<pll> R(N);
 rep(i, N) {
   ll l, r;
   cin >> l >> r;
   ++r; // [l, r) にしておく
   L[i] = {l, r};
   R[i] = {r, l};
 }
 sort(all(L));
 sort(all(R));

 pll maxL = L[N - 1];
 pll minR = R[0];
 ll lgst = 0;  // 一番長い辺
 rep(i, N) chmax(lgst, L[i].second - L[i].first);
 ll llen = max(0LL, minR.first - maxL.first);
 ll ans = lgst + llen; // とりあえず、初日に最長辺+二日目に全部、を候補にする。
 /*
      < >    <= minR/maxLで一緒の場合
     <   >
 */
 if (maxL.first == minR.second && maxL.second == minR.first) { }
 /*
    <   > <= minR
     <   > <= maxL
 */
 else {
   // maxLをとった場合、Rだけ気にすればいい。
   ll l = L[N - 1].first;
   ll r = L[N - 1].second;
   RangeMin sR;  // Rのminを範囲で取得
   sR.init(N);
   rep(i, N) { sR.update(i, R[i].first); }
   RangeMax sL;  // Lのmaxを範囲で取得
   sL.init(N);
   rep(i, N) { sL.update(i, R[i].second); }
   rep(i, N - 1) {
     ll nr = R[N - 1 - i].first;
     if (nr > r) continue;  // 右グループに採用しても上限が変わらない
     ll right = nr - l;
     if (right <= 0) break;  // 右グループが0点になる
     // 右グループに採用すると、点数が減るけど、左グループと加算。
     ll leftR = sR.query(0, N - i - 1);
     ll leftL = sL.query(0, N - i - 1);
     ll left = max(leftR - leftL, 0LL);
     chmax(ans, right + left);
   }
 }
 cout << ans << endl;
}

Submission #29170404 - AtCoder Grand Contest 040