Yukicoder011 カードマッチ

問題概要

一種類$Q$、各種類$H$枚のトランプがある。
今、手札には$N$枚のカードがあり、「手札のカード以外」のマッチするカードの枚数を求めよ。

$N\leqq10^5$、$W,H\leqq10^5$

yukicoder011

解法

$H*W$の領域にカードを1枚置くとすると、その垂直、水平方向にカードをマッチさせることができる。 したがって最終的にできる格子点を数えれば良い。 これは簡単にできて、あるマーク、ある数字のユニークな出現回数を覚えておけば計算できる。

計算量:$O(N)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using PII = pair<int, int>;   using PLL = pair<LL, LL>;
    
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        LL W, H, N;
        cin >> W >> H >> N;
        vector<PLL>sk(N);
        FOR(i, 0, N) {
            cin >> sk[i].first >> sk[i].second;
        }
    
        map<LL, int>mark;
        map<LL, int>num;
        int markcnt = 0;
        int numcnt = 0;
        FOR(i, 0, N) {
            if (mark[sk[i].first] == 0)mark[sk[i].first] = 1, markcnt++;
            if (num[sk[i].second] == 0)num[sk[i].second] = 1, numcnt++;
        }
        LL ans = markcnt * H + numcnt * W - numcnt*markcnt - N;
        cout << ans << "\n";
    
        return 0;
    }