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; }