AGC040 B - Two Contests (600)

B - Two Contests

概要

Ｎ個の区間[Li, Ri]が与えられる。この区間を2つのグループに分け、それぞれのグループごとの区間の共通部分の長さの和の最大値を求めよ。

制約

2 ≦ N ≦ 10^5
1 ≦ Li ≦ Ri ≦ 10^9

方針

maspyさんのブログを参考に考察を進めたい…のですが理解しきれず。。
maspypy.com

とりあえず、てんぷらさんの提出コードで何をやっているか理解してみます。
atcoder.jp

大まかには下記の手順のようです。
①区間[Li, Ri]を左端Liで昇順ソートする
②iまでをグループ1、i+1以降をグループ2として共通部分の長さの和を求め、最大値更新
③iのみをグループ1、それ以外をグループ2として共通部分の長さの和をもとめ、最大値更新

maspyさんの論証につながる部分を感じますが、ここでギブアップ。。

解答

Submission #9362787 - AtCoder Grand Contest 040

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	vector<pll> v(n);
	rep(i, n) cin >> v[i].first >> v[i].second;
	sort(v.begin(), v.end());
 
	ll INF = LLONG_MAX / 2;
	vector<ll> lf(n+1, 0), lb(n+1, 0), rf(n+1, INF), rb(n+1, INF);
	rep(i, n){
		lf[i+1] = max(lf[i], v[i].first);
		rf[i+1] = min(rf[i], v[i].second);
	}
 
	for(int i = n - 1; i >= 0; i--){
		lb[i] = max(lb[i+1], v[i].first);
		rb[i] = min(rb[i+1], v[i].second);
	}
	
	ll ans = 0;
	rep(i, n - 1){
		ans = max(
			ans
			, max(0ll, rf[i+1] - lf[i+1] + 1) 
			+ max(0ll, rb[i+1] - lb[i+1] + 1)
		);
	}
 
	rep(i, n){
		ans = max(
			ans
			, v[i].second - v[i].first + 1 
			+ max(0ll, min(rf[i], rb[i]) - max(lf[i], lb[i]) + 1)
		);
	}
 
	cout << ans << endl;
}