Submission #2116350

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define MOD 1000000007

int main(){
  int R,C,K,N;
  cin>>R>>C>>K>>N;
  int r[N], c[N], nr[R]={},nc[C]={};
  for(int i=0;i<N;i++){
    cin>>r[i]>>c[i];
    r[i]--, c[i]--;
    nr[r[i]]++, nc[c[i]]++;
  }

  int numr[K+1]={}, numc[K+1]={};
  for(int i=0;i<R;i++){
    if(nr[i]>K) continue;
    else numr[nr[i]]++;
  }
  for(int i=0;i<C;i++){
    if(nc[i]>K) continue;
    else numc[nc[i]]++;
  }
  ll ans=0;
  for(int i=0;i<=K;i++){
    ans+=1LL*numr[i]*numc[K-i];
  }
  for(int i=0;i<N;i++){
    int x=nr[r[i]]+nc[c[i]];
    if(x==K){
      ans--;
      //cout<<"- "<<r[i]<<c[i]<<endl;
    }
    else if(x==K+1){
      ans++;
      //cout<<"+ "<<r[i]<<c[i]<<endl;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result