C. Creative Snap 〜10^9を扱うには？二分探索・再帰関数〜

Quiz

https://codeforces.com/contest/1111/problem/C

AC Code

https://codeforces.com/contest/1111/submission/56781314

解法

• 考えている範囲で一気に燃やすコスト
• 考えている範囲を二分割して個別に燃やすコスト
• 上記２つのうち、安い方を選ぶように再帰関数

範囲に何人いる？

// [l, r)
ll how_many(ll l, ll r){
    ll num0 = V.end() - lower_bound(ALL(V), l);
    ll num1 = V.end() - lower_bound(ALL(V), r);
    return num0 - num1;
}

• ソート済みなら二分探索で求まる

TLE 〜再帰関数では明らかな答えは早めにreturnせよ〜

• 分割を最小の粒度まで繰り返すと10⁹個の再帰関数を呼ぶことになり、TLE
• 考えている範囲に人がいないなら、これ以上分割しても意味がないので、分割を考える前にreturnするべし