Submission #1351942

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;
const ll MOD = 1000000000 + 7;

ll mod_pow(const ll &n, ll r){
    if(r == 0) return 1;
    ll ret = mod_pow(n, r / 2);
    ret *= ret;
    ret %= MOD;
    if(r % 2 != 0) ret = ret * n;
    ret %= MOD;
    return ret;
}

// @waring nはMODと互いに素
ll mod_inverse(ll n) {
    return mod_pow(n, MOD - 2);
}

ll mod_factorial(ll n) {
    static vector<ll> memo(100001);
    if(memo[n] > 0) return memo[n];
    if(n <= 1) return 1;
    ll res = n * mod_factorial(n - 1);
    return memo[n] = res;
}


struct UnionFind{
    int n;
    vector<int> p;
    UnionFind(int nn) {
        n = nn;
        p.resize(n);
        rep(i, n) p[i] = i;
    }
    int root(int x) {
        return p[x] == x ? x : (p[x] = root(p[x]));
    }
    void unite(int x,int y) {
        x = root(x); y = root(y);
        if(x != y) p[y] = x;
    }
    bool query(int x,int y){
        return root(x) == root(y);
    }
    vector<vector<int>> get_groups() {
        vector<vector<int>> res;
        vector<bool> visited(p.size());
        rep(i, p.size()) {
            if(!visited[i]) {
                res.push_back(vector<int>());
                rep(j, p.size()) if(query(i, j)) {
                    res.back().push_back(j);
                    visited[j] = true;
                }
            }
        }
        return res;
    }
};

struct S {
    int color, weight, index;    
};
bool operator < (const S &a, const S &b) {
    return a.weight < b.weight;
}
ostream& operator << (ostream &os, const S &a) {
    return os << a.index << " c:" << a.color << " w:" << a.weight << endl;
}

class Solver {
  public:
    bool solve() {
        int N, X, Y; cin >> N >> X >> Y;
        vector<S> in(N);
        rep(i, N) cin >> in[i].color >> in[i].weight;
        sort(all(in));
        rep(i, N) in[i].index = i;
        //cerr << in << endl;
        UnionFind uf(N);
        map<int, S> lightest; // C -> W
        vector<S> lightest2; // 色の異なるボール２個
        // O(n log n)
        rep(i, N) {
            int c = in[i].color, w = in[i].weight;
            //debug(c); debug(w);
            // O(log n)
            if(lightest.count(c) and w + lightest[c].weight <= X) {
                uf.unite(in[i].index, lightest[c].index);
            } else {
                lightest[c] = in[i];
            }
            // O(1)
            rep(j, lightest2.size()) {
                if(c != lightest2[j].color and w + lightest2[j].weight <= Y) {
                    uf.unite(in[i].index, lightest2[j].index);
                }
            }
            if(lightest2.size() == 0) lightest2.push_back(in[i]);
            else if(lightest2.size() == 1 and lightest2[0].color != c) lightest2.push_back(in[i]);
        }
        // O(n)
        auto groups = uf.get_groups();

        ll ans = 1;
        for(auto &g : groups) {
            map<int, int> cnts;
            for(int i : g) cnts[in[i].color]++;
            ans *= mod_factorial(g.size());
            ans %= MOD;
            for(auto p : cnts) {
                // debug(p.second);
                ans *= mod_inverse(mod_factorial(p.second));
                ans %= MOD;
            }
        }

        cout << ans << endl;
        
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}

Submission Info

Judge Result