ABC 186

右に行って下に行くことができるマスをタイプ1、下に行ってから右に行くことができるマスをタイプ2とする。タイプ1かつタイプ2であるようなマスがダブルカウントされているマスである。そのようなマスは、そのマスより左に障害物がなく、そのマスより上にも障害物がないマスである。１行ずつ見ていきながら行にあるマスの列番号に障害物があるかどうかを記録していき、各行にあるダブルカウントしているマスの数を数えればいい。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W, M;
    cin >> H >> W >> M;

    vvll rows(H), cols(W);
    rep(i, M) {
        ll x, y;
        cin >> x >> y;
        x--, y--;
        rows[x].push_back(y);
        cols[y].push_back(x);
    }

    rep(_, 2) {
        rep(i, H) sort(all(rows[i]));
        swap(H, W);
        swap(cols, rows);
    }

    ll ans = 0;
    rep(_, 2) {
        ll fin = H;
        if (cols[0].size()) {
            fin = cols[0][0];
        }
        rep(ri, fin) {
            if (rows[ri].size())
                ans += rows[ri][0];
            else
                ans += W;
        }

        swap(H, W);
        swap(rows, cols);
    }

    auto op = [](ll a, ll b) -> ll { return a + b; };
    auto e = []() -> ll { return 0; };
    segtree<ll, op, e> seg(W);

    ll fin = H;
    if (cols[0].size()) {
        fin = cols[0][0];
    }

    ll r = W;
    if (rows[0].size()) {
        r = rows[0][0];
    }
    rep(ri, fin) {
        ll right = r;
        if (rows[ri].size()) chmin(right, rows[ri][0]);
        ans -= right - seg.prod(0, right);
        for (ll x : rows[ri]) seg.set(x, 1); // 障害物があるマスを 1 にする
    }

    cout << ans << endl;
}

ABC 186

Table of Contents

A. Brick

B. Blocks on Grid

C. Unlucky 7

D. Sum of difference

E. Throne

F. Rook on Grid