Submission #1370259

---

Source Code Expand

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;

template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
/** Interface */
     
inline int readChar();
template <class T = int> inline T readInt(); 
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x ); 
inline void writeWord( const char *s );
     
/** Read */
     
static const int buf_size = 4096;
     
inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len) {
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    }
    if (pos == len) {
        return -1;
    }
    return buf[pos++];
}
     
inline int readChar() {
    int c = getChar();
    while (c <= 32) {
        c = getChar();
    }
    return c;
}
     
template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}
     
/** Write */
     
static int write_pos = 0;
static char write_buf[buf_size];
     
inline void writeChar( int x ) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}
     
template <class T> 
inline void writeInt( T x, char end ) {
    if (x < 0)
        writeChar('-'), x = -x;
     
    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}
     
inline void writeWord( const char *s ) {     while (*s)
writeChar(*s++); }
     
struct Flusher {
    ~Flusher() {
        if (write_pos)
            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;


#define f first
#define s second
#define pb push_back
#define pp pop_back
#define mp make_pair
#define ll long long
#define ld double
#define ull unsigned long long
#define PI pair < int, int > 

const int N = 5e5 + 123;
const int M = 2e5;
const ld Pi = acos(-1);
const ll inf = 1e18;
const int mod = 1e9 + 7;
const int Sz = 501;
const int MOD = 1e9 + 7;

void add(int &a, int b) {
  a += b;
  if (a >= mod) a -= mod;
}
int mult(int a, int b) {
  return 1ll * a * b % mod;
}
int sum(int a, int b) {
  add(a, b);
  return a;
}

int n, X, Y, a[N], b[N], f[N], inv[N], mn[N];
bool used[N];

int cnk(int n, int k) {
  int ans = mult(f[n], inv[k]);
  ans = mult(ans, inv[n - k]);
  return ans;
}

int bp(int a, int n) {
  int ans = 1;
  while(n) {
    if (n & 1) ans = mult(ans, a);
    a = mult(a, a);
    n >>= 1;
  }
  return ans;
}

vector < int > g[N], all, v[N];

int calc(vector < int > a) {
  sort(a.begin(), a.end());
  int n = a.size();
  int ans = 1;
  for (int i = 0;i < a.size();i++) {
    int j = i;
    while(j + 1 < a.size() && a[j + 1] == a[i]) j++;
    int cnt = j - i + 1;
    ans = mult(ans, cnk(n, cnt));
    n -= cnt;
    i = j;
  }
  return ans;
} 
void dfs(int v) {
  used[v] = 1;
  all.pb(a[v]);
  for (auto to : g[v]) if (!used[to]) dfs(to);
}
bool cmp(int i, int j) {
  return b[i] < b[j];
}
void solve() { 
  cin >> n >> X >> Y;
  f[0] = inv[0] = 1;
  for (int i = 1;i <= n;i++) {
    cin >> a[i] >> b[i];
    f[i] = mult(f[i - 1], i);
    inv[i] = bp(f[i], mod - 2);
    v[a[i]].pb(i);
  }
  vector < int > tmp;
  for (int i = 1;i <= n;i++) {
    sort(v[i].begin(), v[i].end(), &cmp);
    for (int j = 1;j < v[i].size();j++) {
      int f = v[i][j];
      int s = v[i][0];
      if (b[f] + b[s] <= X) {
        g[f].pb(s);
        g[s].pb(f);
      }
    }
    if (v[i].size()) {
      tmp.pb(v[i].front());
    }
  }
  sort(tmp.begin(), tmp.end(), &cmp);
  for (int j = 1;j < tmp.size();j++) {
    int f = tmp[0];
    int s = tmp[j];
    if (b[f] + b[s] <= Y) {
      g[f].pb(s);
      g[s].pb(f);
    }
    if (j > 1) {
      int f = tmp[1];
      int s = tmp[j];
      if (b[f] + b[s] <= Y) {
        g[f].pb(s);
        g[s].pb(f);
      }
    }
  }
  int ans = 1;
  for (int i = 1;i <= n;i++) {
    if (!used[i]) {
      all.clear();
      dfs(i);
      ans = mult(ans, calc(all));
    }
  }
  cout << ans << endl;
}

int main() {
  #ifdef wws
   freopen("in", "r", stdin);
   // freopen("in", "w", stdout);
  #endif 
  ios_base::sync_with_stdio(0);
  int tt = 1; 
  while(tt--) solve();
  return 0;
}

Submission Info

Judge Result