ARC023 C問題 収集王

盤面のある行とある列を足してKとなる組み合わせの数を出力する問題。
すごい簡単そうなんだけど、普通にやろうとするとO(R*C)でR,Cが10^5なのでTLE
どう考えるかというと、盤面ではなくて、飴のあるマスに関してだけ注意を配る。
単純に足し合わせがKになる場所の数を求めたら、飴のあるマスに関してだけそれを修正していけばO(R+C+N)で間に合う。
これができなかったのはちょっとつらい。

#include<bits/stdc++.h>
using namespace std;
#define len(val) static_cast<long long>(val.size())
#define rep(i, n) for(int i=0; i<(n); i++)
typedef long long ll;
typedef pair<int, int> P;


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

    int R, C, K; cin >> R >> C >> K;
    int N; cin >> N;
    vector<P> B;
    int sumR[R], sumC[C];
    memset(sumR, 0, sizeof(sumR));
    memset(sumC, 0, sizeof(sumC));

    for(int i=0; i<N; i++){
        int r, c; cin >> r >> c; r--; c--;
        B.push_back(P(r, c));
        sumR[r]++;
        sumC[c]++;
    }
    map<int, ll> mapR, mapC;
    for(int i=0; i<R; i++){
        mapR[sumR[i]]++;
    }
    for(int i=0; i<C; i++){
        mapC[sumC[i]]++;
    }
    ll res = 0;
    for(int i=0; i<=K; i++){
        res += mapR[i]*mapC[K-i];
    }
    for(auto v : B){
        if(sumR[v.first]+sumC[v.second] == K) res--;
        else if(sumR[v.first]+sumC[v.second] == K+1) res++;
    }
    cout << res << endl;
}