Submission #2107175

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define int LL
using namespace std;
typedef long long LL;
const LL mo=1e9+7;
const int INF=1e18;
LL fac[500001],inv[500001];
int n,x,y,fa[500001],p[500001];
vector <int> v[500001],id[500001],ans[500001];
struct data {
    int c,w;
}a[500001];
bool cmp(int x,int y) {
    int ux,vx;
    if (v[x].size()==0) ux=INF;else ux=v[x][0];
    if (v[y].size()==0) vx=INF;else vx=v[y][0];
    return ux<vx;
}
LL mul(LL x,LL y) {
    if (y==0) return 1;
    LL now=mul(x,y/2);
    now=now*now%mo;
    if (y%2) return now*x%mo;
    return now;
}
void pre() {
    fac[0]=1;
    for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mo;
    inv[n]=mul(fac[n],mo-2);
    for (int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mo;
}
int getf(int x) {
    if (fa[x]==x) return x;
    fa[x]=getf(fa[x]);
    return fa[x];
}
void unio(int u,int v) {
    int fu=getf(u),fv=getf(v);
    if (fu==fv) return;
    fa[fu]=fv;
}
main() {
    scanf("%lld%lld%lld",&n,&x,&y);
    pre();
    for (int i=1;i<=n;i++) {
        scanf("%lld%lld",&a[i].c,&a[i].w);
        v[a[i].c].push_back(a[i].w);
        id[a[i].c].push_back(i);
    }
    for (int i=1;i<=n;i++)
        sort(v[i].begin(),v[i].end());
    for (int i=1;i<=n;i++) fa[i]=p[i]=i;
    sort(p+1,p+n+1,cmp);
    for (int i=1;i<=n;i++) {
        if (v[i].size()==0) continue;
        int wx=max(x-v[i][0],y-v[p[1]][0]);
        int lx=0,rx=v[i].size()-1;
        while (lx<rx) {
            int mid=(lx+rx+1)/2;
            if (v[i][mid]<=wx) lx=mid;
            else rx=mid-1;
        }
        for (int j=0;j<lx;j++) unio(id[i][j],id[i][j+1]);
    }
    int wx=y-v[p[1]][0];
    int lx=1,rx=n;
    while (lx<rx) {
        int mid=(lx+rx+1)/2;
        int now;
        if (!v[p[mid]].size()) now=INF;
        else now=v[p[mid]][0];
        if (now<=wx) lx=mid;
        else rx=mid-1;
    }
    for (int i=1;i<lx;i++) unio(id[p[i]][0],id[p[i+1]][0]);
    for (int i=1;i<=n;i++) ans[getf(i)].push_back(a[i].c);
    LL ansx=1;
    for (int i=1;i<=n;i++) {
        if (getf(i)!=i) continue;
        sort(ans[i].begin(),ans[i].end());
        ansx=ansx*fac[ans[i].size()]%mo;
        for (int j=0;j<ans[i].size();) {
            int kx=j;
            while (ans[i][j]==ans[i][kx]&&kx<ans[i].size()) kx++;
            ansx=ansx*inv[kx-j]%mo;
            j=kx;
        }
    }
    printf("%lld\n",ansx);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:48:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld",&n,&x,&y);
                                   ^
./Main.cpp:51:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&a[i].c,&a[i].w);
                                          ^

Judge Result