AOJ 1386 Starting a Scenic Railroad Service

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1386

解法

一方はいもす法やるだけなのはすぐわかると思います．
もう一方が問題ですが，これも累積和で簡単に求まります．
じつは，乗客 i のデータの区間 [a[i], b[i]] に対して，端点以外で少しでもかぶっている他の乗客の区間の数を M_i とすると，M = max{ M_i } が答えになります．

以下ちゃんとした（仰々しい）証明．
求めたい答えを A とすると，A >= M である．区間 [a[i], b[i]] に少しでもかぶる乗客の集合を S_i (これには乗客 i も含める) とする．S_i のうち，互いに区間がかぶらない乗客が優先的に予約をしていくと考えれば，少なくとも |S_i| 席が必要である．仮に s ( < |S_i| ) 席しかないとする．互いに区間がかぶらない乗客の数が s 人以上であれば，そのうちの s 人で先に席を埋めてしまうと，乗客 i が予約できなくなるので，s 席では足りない．乗客の数が s 人未満でも同じ．よって，A >= |S_i| だから A >= M が示せた．
次に A <= M であることを示す．とはいっても明らかで，ある区間に同時にのる乗客の数以上の席は明らかに必要ない．

以上より，A = M = max{ |S_i| } であり，累積和で求めることができる．
具体的には順方向の累積和 sum[i] ( b[i] を用いる ) と逆方向の累積和 rsum[i] ( a[i] を用いる ) を用意すれば良い．この時，
sum[i] := 区間 [0..i] に完全に含まれる乗客の数
rsum[i] := 区間 [i...] に完全に含まれる乗客の数
になる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    int MAX = 1e5 + 2;
    vector<int> a(n), b(n);
    vector<int> imos(MAX), sum(MAX), rsum(MAX);
    for(int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        imos[a[i]]++;
        imos[b[i]]--;
        sum[b[i]]++;
        rsum[a[i]]++;
    }
    for(int i = 1; i < MAX; ++i) {
        imos[i] += imos[i - 1];
        sum[i] += sum[i - 1];
    }
    for(int i = MAX - 1; i >= 1; --i) {
        rsum[i - 1] += rsum[i];
    }
    int ans1 = 0, ans2 = *max_element(imos.begin(), imos.end());
    for(int i = 0; i < n; ++i) {
        ans1 = max(ans1, n - sum[a[i]] - rsum[b[i]]);
    }
    cout << ans1 << ' ' << ans2 << endl;
}

感想

本番ではチームメイトが累積和のやり方を考えてくれて，僕が正当性を詰めました．
詰めると言っても流石にここまで丁寧に詰めたわけではないですが…