比赛 USACO2026 JAN G&P2 评测结果 WWWAWWWWWWWWWWWW
题目名称 Supervision 最终得分 6
用户昵称 LikableP 运行时间 2.475 s
代码语言 C++ 内存使用 15.70 MiB
提交时间 2026-01-24 11:05:42
显示代码纯文本
#include <cstdio>
#include <cctype>
#include <vector>

template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}
 
typedef long long ll;

const int MAXN = 1e6 + 10;
const ll MOD = 1e9 + 7;

ll pow2[MAXN];
void Initialize() {
  pow2[0] = 1;
  for (int i = 1; i <= MAXN - 10; ++i) {
    pow2[i] = (pow2[i - 1] * 2) % MOD;
  }
}

int n, d;
int place[MAXN], indentity[MAXN];
int couchCount;
ll ans;

int main() {
  #ifdef LOCAL
    freopen("!input.in", "r", stdin);
    freopen("!output.out", "w", stdout);
  #else
    freopen("Supervision.in", "r", stdin);
    freopen("Supervision.out", "w", stdout);
  #endif

  Initialize();
  
  n = read<int>(), d = read<int>();
  for (int i = 1; i <= n; ++i) {
    place[i] = read<int>(), indentity[i] = read<int>();
    couchCount += indentity[i];
  }

  if (d == 0) {
    printf("%lld\n", (pow2[couchCount] - 1 + MOD) % MOD);
    return 0;
  }

  for (int mask = 0; mask < 1 << n; ++mask) {
    std::vector<int> choose(1, 0);
    for (int i = 1; i <= n; ++i) if ((mask >> (i - 1)) & 1) choose.push_back(i);
    bool ok = true;
    for (int i = 1; i < (int) choose.size(); ++i) {
      if (indentity[choose[i]]) continue;
      for (int j = i - 1; j >= 1 && place[choose[i]] - place[choose[j]] >= d; --j) if (indentity[choose[j]]) continue;
      ok = false;
      break;
    }
    if (ok) if (++ans == MOD) ans = 0;
  }

  printf("%lld\n", ans);
  return 0;
}