T0609 涂色游戏

#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, T;
    cin >> n >> m >> T;

    // 每行/列最后一次涂色的时间与颜色
    vector<int> rt(n + 1, 0), rc(n + 1, 0);
    vector<int> ct(m + 1, 0), cc(m + 1, 0);
    for (int t = 1; t <= T; ++t) {
        int op, x, c;
        cin >> op >> x >> c;
        if (op == 1) {
            rt[x] = t;
            rc[x] = c;
        } else {
            ct[x] = t;
            cc[x] = c;
        }
    }

    vector<int> rts, cts;
    for (int i = 1; i <= n; ++i) rts.push_back(rt[i]);
    for (int j = 1; j <= m; ++j) cts.push_back(ct[j]);
    sort(rts.begin(), rts.end());
    sort(cts.begin(), cts.end());

    // 颜色编号不超过 2e5
    vector<long long> num(200001, 0);
    for (int i = 1; i <= n; ++i) {
        // 这一行里，列的最后一次涂色不晚于行的格子数（由行决定颜色）
        long long k = upper_bound(cts.begin(), cts.end(), rt[i]) - cts.begin();
        num[rc[i]] += k;
    }
    for (int j = 1; j <= m; ++j) {
        // 这一列里，行的最后一次涂色更早的格子数（由列决定颜色）
        long long k = lower_bound(rts.begin(), rts.end(), ct[j]) - rts.begin();
        num[cc[j]] += k;
    }

    int kinds = 0;
    for (int c = 0; c <= 200000; ++c)
        if (num[c] > 0) kinds++;
    cout << kinds << "\n";
    for (int c = 0; c <= 200000; ++c)
        if (num[c] > 0) cout << c << " " << num[c] << "\n";
    return 0;
}