回転寿司 [第三回 アルゴリズム実技検定 J]

https://atcoder.jp/contests/past202005-open/tasks/past202005_j

前提知識

• セグメントツリー
• 二分探索

解説

https://atcoder.jp/contests/past202005-open/submissions/14068492

最初に「まだお寿司を1つを食べていない」という条件は、
自分の過去最高美味しさを-1とでもしておけば無視できるので、そういう感じに変えておく。
あるお寿司を食べる子供は、それより前の子供がスルーして、かつ、自分の過去最高美味しさより大きい場合である。
それより前の子供がスルーというのがいまいちなので言い換えると、
「それより前の子供の過去最高美味しさの最小値が、今のお寿司以上」
の場合である。
もっと言い換えると、
「(今のお寿司)≦(ある子どもより前の子供の過去最高美味しさの最小値)、かつ、(ある子供の過去最高美味しさ)＜(今のお寿司)」
であれば、その子が食べる。

ここまで考察が進めば、あとはデータ構造を知っているかの問題になる。
区間最小値のセグメントツリーを使おう。
segtree[i] := 先頭からi番目の子供の過去最高美味しさ
これと二分探索を使って、
「(今のお寿司)≦(ある子どもより前の子供の過去最高美味しさの最小値)、かつ、(ある子供の過去最高美味しさ)＜(今のお寿司)」
の境界線を探す。
これで誰が食べるかは分かるので答えて、セグメントツリーの食べた子の部分を記録更新しておく。

int N, M, A[301010];
SegTree<int, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> A[i];

    rep(i, 0, N) st.update(i, 0);
    rep(i, 0, M) {
        int ng = 0, ok = N + 1;
        while (ng + 1 != ok) {
            int md = (ng + ok) / 2;
            if (st.get(0, md) < A[i]) ok = md;
            else ng = md;
        }
        if (ok != N + 1) {
            int eat = ok - 1;
            st.update(eat, A[i]);
            printf("%d\n", eat + 1);
        }
        else printf("-1\n");
    }
}