かえるのうた [yukicoder 871]

https://yukicoder.me/problems/no/871

前提知識

• 二分探索
• BFS

解説

https://yukicoder.me/submissions/374448

シミュレーションを考えてみる。
あるカエルが鳴くとそれに共鳴するのは、とある区間のカエルになる。
どこからどこまでのカエルかどうかの端点は二分探索で高速に探すことができる。
まだチェックしていないカエルがいたら、そのカエルについても共鳴するカエルの区間を求める。
これを繰り返していく。
1カエルについて共鳴調査は1回でいいため、N匹のカエルについて二分探索するので、O(NlogN)
BFSのような操作になる。

int N, K; ll X[101010], A[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K; K--;
    rep(i, 0, N) cin >> X[i];
    rep(i, 0, N) cin >> A[i];

    int L = K, R = K;
    queue<int> que;
    que.push(K);

    int ans = 0;
    while(!que.empty()) {
        int cu = que.front(); que.pop();
        ans++;

        int l = lower_bound(X, X + N, X[cu] - A[cu]) - X;
        int r = upper_bound(X, X + N, X[cu] + A[cu]) - X - 1;

        while (l < L) {
            L--;
            que.push(L);
        }

        while (R < r) {
            R++;
            que.push(R);
        }
    }
    cout << ans << endl;
}