Noip 2019合宿テスト試合(21)Problem A:Colorful Balls

Problem A: Colorful Balls

Description

Snukeが放した
N個一列カラーのボール左からi番目のボールの色はci重量ですwi彼女は2つの操作を実行することによってこれらのボールを並べ替えることができます1:同じ色のボールを2つ選択して、もし彼らの重量とX以下ならば、2つのボールを交換する位置操作2:2つの異なる色のボールを選択して、もし彼らの重量とY以下ならば、2つのボールを交換する位置は私たちが全部で何種類の異なる色のシーケンスを得ることができますか?答えに対して109+7の型を取る

Input

N X Yc1 w1.
.
.cN wN

Output

答えを出力します.

Sample Input

sample input 1:
4 7 3
3 2
4 3
2 1
4 4
sample input 2:
1 1 1
1 1
sample input 3:
21 77 68
16 73
16 99
19 66
2 87
2 16
7 17
10 36
10 68
2 38
10 74
13 55
21 21
3 7
12 41
13 88
18 6
2 12
13 87
1 9
2 27
13 15

Sample Output

sample output 1:
2
sample output 2:
1
sample output 3:
129729600

HINT

1≤N≤2×105
1≤X,Y≤1091≤ci≤N1≤wi≤109

ぶんせき

まず、ボールAがボールBと交換できる場合、ボールBもボールCと交換できる場合、必ずボールBを通じてボールAとボールCを交換することができる.
したがって、交換可能な任意の2つのボールの間に1つの辺をつなぎ、各連結ブロックの各球色の個数を探し出すだけで、各連結ブロック内はどのように並べてもよいので、現在の連結ブロックに合法的に配列されている案数を組合せ数で求めることができ、最後にすべての連結ブロックの案数を乗じて答えを得ることができる.
しかし,この方法の時間的複雑さはO(n 2)である.
しかし、私たちは以下のように設定することができます.
ボールaは全球の中で最も重量の小さいボールである.
ボールbは、全球においてボールaとは色が異なり、重量が最も小さいボールである.
ボールbが見つからないと、1色のボールしかないので、1つの案しかありません
ボールaとボールbが同一の連通ブロック内にないと、2つの異なる色のボールが同一の連通ブロック内に現れることは不可能であるため、1つのスキームしかない
各ボールにとって、ボールaにもbにもつながっていなければ、他の異色のボールにもつながっていない.
だから1つのインターフェースブロックだけが答えに貢献する可能性があります.
だから、私たちはボールaやボールbにつながったり、それと同じ色でボールaやボールbにつながったりできるすべてのボールを求めるだけです.
時間複雑度O(n)
O(n)の時間は組み合わせの数を求めて詳しくオーラの定理を参照します

#include
#include
#include
using namespace std;
struct data{
    long long x,y;
}t[300001];
long long n,s1,s2,k1,k2,f[300001],k[300001],m=1000000007,s[300001],cnt,id[300001],sum,ans=1,col[300001],colmax[300001];
bool d[300001],r[300001];
bool cmp(data a,data b){
    return a.y<b.y;
}
long long get_pow(long long a,long long b){
    long long p=1;
    while(b){
        if(b%2)p=(p*a)%m;
        a=(a*a)%m;
        b=b/2;
    }
    return p;
}
long long c(long long a,long long b){
    return (((k[a]*f[b])%m)*f[a-b])%m;
}
void add(long long a){
    long long p=a;
    while(t[col[p]].y+t[a].y<=s1){
        if(!col[p])break;
        s[t[a].x]++;
        sum++;
        p=col[p];
        r[p]=1;
    }
}
int main(){
    scanf("%lld%lld%lld",&n,&s1,&s2);
    k[0]=1;
    for(long long i=1;i<=n;i++)k[i]=(k[i-1]*i)%m;
    f[n]=get_pow(k[n],m-2);
    for(long long i=n-1;i>1;i--)f[i]=(f[i+1]*(i+1))%m;
    f[0]=1;
    f[1]=1;
    for(long long i=1;i<=n;i++)scanf("%lld%lld",&t[i].x,&t[i].y);
    sort(t+1,t+n+1,cmp);
    for(long long i=1;i<=n;i++){
        col[colmax[t[i].x]]=i;
        colmax[t[i].x]=i;
    }
    k1=1;
    k2=2;
    while(k2<=n&&t[k2].x==t[k1].x)k2++;
    if(k2!=n+1){
        if(t[k1].y+t[k2].y<=s2){
            for(long long i=1;i<=n;i++){
                if((t[i].x!=t[k1].x&&t[k1].y+t[i].y<=s2)||(t[i].x!=t[k2].x&&t[k2].y+t[i].y<=s2)){
                    if(!d[t[i].x]){
                        d[t[i].x]=1;
                        r[i]=1;
                        cnt++;
                        id[cnt]=t[i].x;
                        s[t[i].x]++;
                        sum++;
                        add(i);
                    }else if(!r[i]){
                        s[t[i].x]++;
                        r[i]=1;
                        sum++;
                    }
                }
            }
            for(long long i=1;i<=cnt;i++){
                ans=(ans*c(sum,s[id[i]]))%m;
                sum=sum-s[id[i]];
            }
        }
    }
    printf("%lld
",ans);
}