Educational Codeforces Round 40 F. Runner's Problem

実装でハマった箇所があったので念のため書いておきます…
(僕と同じミスをした人の助けになれば幸いです)

解説

結論から書きます.問題文にひっそり書いてあるこの文章.

Some cells may be blocked by multiple obstacles.

これに対応したコードを書かないと死にます.以上.

…もう少し書きます.

僕の場合,障害物による行列の変更にイベントソートを使ったのですが, 障害物の区間が終わるタイミングで「セルを解放する(禁止を解除する)」と実装すると, 区間が重なっていた場合に勝手な解放を許してしまうことになり答えが合わなくなります *1

よって,例えば「いま  i 行目には禁止区間がいくつ重なっているか?」を管理して,この値が  1 以上の時に行列要素を  0 にすればよいです.

所感

問題文に書いてある意味深な文章には注意しよう.

解答例

https://codeforces.com/contest/954/submission/114687102

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    ll N, M; cin >> N >> M;

    // イベントソート
    map<ll,VP> mp;
    REP(_,N) {
        ll a, l, r; cin >> a >> l >> r;
        a--; l--; r--;
        mp[l  ].push_back(P(+1,a));  // 禁止区間の追加
        mp[r+1].push_back(P(-1,a));  // 禁止区間の削除
    }
    mp[M].push_back(P(0,0));

    VVM B = {{1, 0, 0},
             {0, 1, 0},
             {0, 0, 1}};

    VVM A = {{1, 1, 0},
             {1, 1, 1},
             {0, 1, 1}};

    ll pos = 0;
    VLL X(3,0);  // 禁止カウント (>0 のとき禁止)
    for (auto& [x, E] : mp) {
        ll n = x-1 - pos;
        B = mat_mul(mat_exp(A, n), B);
        pos = x-1;

        for (auto [q, y] : E) {
            if (q == -1) {
                X[y]--;
                if (X[0] == 0) A[0] = {1, 1, 0};
                if (X[1] == 0) A[1] = {1, 1, 1};
                if (X[2] == 0) A[2] = {0, 1, 1};
            } else if (q == 1) {
                X[y]++;
                if (X[0] > 0) A[0] = {0, 0, 0};
                if (X[1] > 0) A[1] = {0, 0, 0};
                if (X[2] > 0) A[2] = {0, 0, 0};
            }
        }
    }

    mint ans = B[1][1];
    COUT(ans);

    return 0;
}

*1:僕の場合は test 3 ケースで WA になりました