Codeforces Round 879 (Div. 2) - D. Survey in Class

D. Survey in Class

항상 어떤 구간 하나만 전체적으로 모두 써서 정답을 만들 수 있음을 관찰한다.

그리고 알아내야 하는건 그 구간과 어떤 다른 구간이 최대로 안겹치는 길이이다.

구간이 겹치는 경우는 총 네가지이다.

• 완전히 포함
• 완전히 미포함
• 왼쪽만 겹침
• 오른쪽만 겹침

$2,3,4$ 번을 처리해주기 위해 $l_i$중 최대값과 $r_i$ 중 최소값을 기록한다.

현재 보고있는 구간에서 $\text{Min}(r_i-l_i+1, l_\text{Max}-l_i)$ 를 보면 오른쪽으로 완전히 미포함되거나 오른쪽만 겹치는 경우를 처리해줄 수 있다.

반대로 $\text{Min}(r_i-l_i+1, r_i-r_\text{Min})$ 을 고려하면 왼쪽으로 완전히 미포함되거나 왼쪽만 겹치는 경우를 처리해줄 수 있다.

완전히 포함되는 경우를 처리하려면 $r_i-l_i+1$ 중 최소값을 기록하고 모든 구간에서 그만큼 빼보면 된다.

void solved() {
   int n, m;
   cin >> n >> m;
   vector<pi> a(n);
   for (auto &[l, r]: a) cin >> l >> r;
   int ans = 0;
 
   int maxL = 0, minR = 1e9, mn_len = 1e9;
   for (auto [l, r]: a) maxa(maxL, l), mina(minR, r), mina(mn_len, r - l + 1);
   for (int i = 0; i < n; i++) {
      maxa(ans, a[i].se - a[i].fi + 1 - mn_len);
      maxa(ans, min(a[i].se - a[i].fi + 1, a[i].se - minR));
      maxa(ans, min(a[i].se - a[i].fi + 1, maxL - a[i].fi));
   }
   cout << ans * 2 << endl;
}