Submission #3245152

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int inf = 1e9;
const int mod = 1e9 + 7;

inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }

inline int sub(int a, int b) { return a >= b ? a - b : a - b + mod; }

inline int mul(int a, int b) { return llint(a) * b % mod; }

int powmod(int a, int b) {
  if (b == 0) return 1;
  if (b % 2) return mul(a, powmod(a, b - 1));
  return powmod(mul(a, a), b / 2);
}

int main(void) {
  ios_base::sync_with_stdio(false);

  int N, X, Y;
  cin >> N >> X >> Y;

  vector<int> fact(N + 1);
  fact[0] = 1;
  for (int i = 1; i <= N; ++i) {
    fact[i] = mul(fact[i - 1], i);
  }

  vector<vector<int>> W(N);
  REP(i, N) {
    int c, w;
    cin >> c >> w;
    W[c - 1].push_back(w);
  }

  int minW1 = inf;
  int minW2 = inf;
  for (auto& w : W) {
    if (w.size() > 0) {
      sort(w.begin(), w.end());
      if (w[0] <= minW1)
        minW2 = minW1, minW1 = w[0];
      else if (w[0] <= minW2)
        minW2 = w[0];
    }
  }

  vector<pair<int, int>> a;
  for (auto& w : W) {
    if (w.size() > 0) {
      int L = X - w[0];
      if (w[0] == minW1) {
        L = max(L, Y - minW2);
      } else {
        L = max(L, Y - minW1);
      }

      while (w.size() > 0 && w.back() > L) w.pop_back();
      if (w.size() > 0) a.push_back({w[0], w.size()});
    }
  }

  if (a.size() == 0) {
    cout << "1\n";
    return 0;
  }

  sort(a.begin(), a.end());
  int r = 1;
  while (r < (int)a.size() && a[r].first + a[0].first <= Y) r++;

  int s = 0, denom = 1;
  REP(i, r) {
    s += a[i].second;
    denom = mul(denom, fact[a[i].second]);
  }

  int ret = mul(fact[s], powmod(denom, mod - 2));
  cout << ret << "\n";
  return 0;
}

Submission Info

Judge Result