Submission #3459723

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 1100000000

using namespace std;

int main()
{
  int R, C, K;
  int N;
  cin >> R >> C >> K;
  cin >> N;
  vector<int> srow(R, 0);
  vector<vector<int>> row(R);
  // scol[i] = (アメの和, 見ている列)
  vector<pair<int, int>> scol;
  for (int i = 0; i < C; i++) {
    scol.push_back(make_pair(0, i));
  }

  for (int i = 0; i < N; i++) {
    int r, c;
    cin >> r >> c;
    r--; c--;
    srow[r]++;
    scol[c].first++;
    row[r].push_back(c);
  }
  sort(scol.begin(), scol.end());

  int ans = 0;
  for (int i = 0; i < R; i++) {
    int rest = K - srow[i];
    int idx = lower_bound(scol.begin(), scol.end(), make_pair(rest, -INF)) - scol.begin();
    while (scol[idx].first == rest) {
      // 交差点にアメが無かったらans++
      int cpos = scol[idx].second;
      auto rpos = find(row[i].begin(), row[i].end(), cpos);
      if (rpos == row[i].end()) ans++;
      idx++;
    }

    idx = lower_bound(scol.begin(), scol.end(), make_pair(rest + 1, -INF)) - scol.begin();
    while (scol[idx].first == rest + 1) {
      // 交差点にアメがあったらans++
      int cpos = scol[idx].second;
      auto rpos = find(row[i].begin(), row[i].end(), cpos);
      if (rpos != row[i].end()) ans++;
      idx++;
    }
  }
  cout << ans << endl;

  return 0;
}

Submission Info

Judge Result