ABC 346

Table of Contents

https://atcoder.jp/contests/abc346

A. Adjacent Product

https://atcoder.jp/contests/abc346/tasks/abc346_a

B. Piano

https://atcoder.jp/contests/abc346/tasks/abc346_b

C. Σ

https://atcoder.jp/contests/abc346/tasks/abc346_c

D. Gomamayo Sequence

https://atcoder.jp/contests/abc346/tasks/abc346_d

E. Paint

https://atcoder.jp/contests/abc346/tasks/abc346_e

クエリを逆順に処理すると次のような問題を解くことと今回の問題は同値になる。

こうすると行を処理するときは、その行がすでに処理されていれば skip、そうでなければ $( \text{列数} ) - ( \text{今まで塗られた列の数} )$ 個のマスが色 $X_i$ に塗られることになる。同様に列を処理するときは $( \text{行数} ) - ( \text{今まで塗られた行の数} )$ 個のマスが色 $X_i$ に塗られることになる。

何にも塗られていないマスの数は、最終的に $( \text{行数} ) - ( \text{今まで塗られた行の数} )$ と $( \text{列数} ) - ( \text{今まで塗られた列の数} )$ の積になる。

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

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

    vint usedr(H), usedc(W);
    vll numcolor((int)2e5 + 5);
    ll numr = 0, numc = 0;

    vector<tuple<ll, ll, ll>> qs;
    rep(i, M) {
        ll t, a, x;
        cin >> t >> a >> x;
        a--;
        qs.emplace_back(t, a, x);
    }

    reverse(all(qs));
    for (auto [t, a, x] : qs) {
        if (t == 1) {
            if (usedr[a]) continue;
            usedr[a] = 1;
            numcolor[x] += W - numc;
            numr++;
        } else {
            if (usedc[a]) continue;
            usedc[a] = 1;
            numcolor[x] += H - numr;
            numc++;
        }
    }

    numcolor[0] += (H - numr) * (W - numc);
    vector<pair<ll, ll>> ans;
    rep(i, (ll)numcolor.size()) {
        if (numcolor[i]) {
            ans.emplace_back(i, numcolor[i]);
        }
    }

    cout << ans.size() << endl;
    for (auto [c, num] : ans) cout << c << ' ' << num << '\n';
}

F. SSttrriinngg in StringString

https://atcoder.jp/contests/abc346/tasks/abc346_f

G. Alone

https://atcoder.jp/contests/abc346/tasks/abc346_g