srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ABC 014 C - AtColor

問題

問題概要

もっとも多くの区間に含まれている数字を囲んでいる区間の総数を求める問題。

解法

区間が始まる点を+1、区間が終わる点を-1することで、[a, b]をインクリメントする必要がなくなり、最後に一度だけ、全体をなめるだけで、最大数がわかる。

ミス

なんかやったことある。

コード

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

int n, cnt[1000010];

int main(void){
    cin >> n;
    rep(i, n) cnt[i] = 0;
    rep(i, n){
        int a, b; cin >> a >> b;
        b++;
        cnt[a]++; cnt[b]--;
    }

    int ans = 0, now = 0;
    rep(i, 1000010){
        now += cnt[i];
        ans = max(ans, now);
    }
    cout << ans << endl;
    return 0;
}