C - 収集王 / AtCoderBeginnerContest#023

abc023.contest.atcoder.jp

#include <iostream>
#include <vector>
using namespace std;

#define MAX 100000
typedef pair<int,int> P_II;

void Solve(int r, int c, int k) {
    int n, rr, cc, row[MAX+1]={0}, col[MAX+1]={0}, count_row[MAX+1]={0}, count_col[MAX+1]={0};
    long long answer=0;
    vector<P_II> data(MAX);

    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> rr >> cc;
        ++row[rr-1]; ++col[cc-1];
        data[i]=make_pair(cc-1,rr-1);
    }
    for (int i=0; i<c; ++i)
        ++count_col[ col[i] ];
    for (int j=0; j<r; ++j)
        ++count_row[ row[j] ];
    for (int i=0; i<=k; ++i)
        answer+=count_row[i]*count_col[k-i];
    for (int i=0; i<n; ++i) {
        P_II p_ii=data[i];
        long long count=col[p_ii.first]+row[p_ii.second];
        if (count == k) --answer;
        else if (count == k+1)  ++answer;
    }
    cout << answer << endl;
}

int main(void)  {
    int r, c, k;

    cin >> r >> c >> k;
    Solve(r,c,k);
    return 0;
}

列と行を足した答えがkになる数を数える。
起点では重複しているのでkの場合は-1、k+1の場合は+1。
〜了〜