Atcoder提交记录

WA on #50,51,53,54

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int maxn = 5e5 + 10, mod = 1e9 + 7;
int n, x, y, cmin1 = 1, cmin2 = 1, ans = 1;
int c[maxn], w[maxn], wmin[maxn], cnt[maxn];
vector<int> col[maxn];
namespace DSU
{
    int fa[maxn];
    bool vis[maxn];
    vector<int> dsu[maxn];
    int find(int x)
    {
        if (x == fa[x])
            return x;
        return fa[x] = find(fa[x]);
    }
    void join(int x, int y)
    {
        // printf("**%d %d\n",x,y);
        int fx = find(x), fy = find(y);
        // if (fx != fy)
            fa[fx] = fy;
        return;
    }
}
using namespace DSU;

namespace Init
{
    int fac[maxn], inv[maxn], ifac[maxn];
    queue<int> in;
    int qpow(int x, int y)
    {
        if (y == 0)
            return 1;
        int a = qpow(x, y / 2);
        if (y & 1)
            return a * a % mod * x % mod;
        else
            return a * a % mod;
    }
    void init()
    {
        for (int i = 1; i < maxn; i++)
            fa[i] = i;
        fac[0] = ifac[0] = inv[1] = 1;
        for (int i = 1; i < maxn; i++)
        {
            if (i > 1)
                inv[i] = inv[mod % i] * (mod - mod / i) % mod;
            fac[i] = fac[i - 1] * i % mod;
            ifac[i] = ifac[i - 1] * inv[i] % mod;
        }
    }
    void back()
    {
        while (!in.empty())
        {
            // printf("%d %d\n",in.front(),cnt[c[in.front()]]);
            cnt[c[in.front()]] = 0;
            in.pop();
        }
        return;
    }
}
using namespace Init;
signed main()
{
    scanf("%lld%lld%lld", &n, &x, &y);
    init();
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld", &c[i], &w[i]);
        col[c[i]].pb(i);
        if (w[i] < w[wmin[c[i]]] || wmin[c[i]] == 0)
            wmin[c[i]] = i;
        if (w[i] <= w[cmin1])
            cmin2 = cmin1, cmin1 = i;
        if (w[i] > w[cmin1] && w[i] < w[cmin2])
            cmin2 = i;
    }
    // printf("%d %d\n",cmin1,cmin2);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < col[i].size(); j++)
        {
            if (col[i][j] != wmin[i] && w[col[i][j]] + w[wmin[i]] <= x)
            {
                join(col[i][j], wmin[i]);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (c[i] != c[cmin1] && w[i] + w[cmin1] <= y)
            join(i, cmin1);
        if (c[i] != c[cmin2] && w[i] + w[cmin2] <= y)
            join(i, cmin2);
    }
    for (int i = 1; i <= n; i++)
    {
        dsu[find(i)].pb(i);
    }
    for (int i = 1; i <= n; i++)
    {
        int siz = 0;
        back();
        for (int j = 0; j < dsu[i].size(); j++)
        {
            int u = dsu[i][j];
            // printf("%d ",dsu[i][j]);
            ans = ans * fac[cnt[c[u]]] % mod * ifac[siz] % mod;
            siz++;
            cnt[c[u]]++;
            ans = ans * fac[siz] % mod * ifac[cnt[c[u]]] % mod;
            in.push(u);
        }
        // puts("");
        // if(dsu[i].size()) printf("**%lld\n",siz);
    }
    printf("%lld", ans);
}