Submission #2835145

---

Source Code Expand

#include "bits/stdc++.h"
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define pii pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
ll int MOD=1e9+7;
#define INF 2*1e9
#define N 310000 
using namespace std;
string alphabet("abcdefghijklmnopqrstuvwxyz");
ll int inv[N*2],comb[N*2];
void calc_inv(ll n){
    inv[1]=1;
    rep2(i,2,n*2){
        inv[i]=((-(MOD/i)*inv[MOD%i])%MOD+MOD)%MOD;
    }
    return;
}

main(){
    ll n;
    ll x,y;
    cin>>n>>x>>y;
    pii p[N];
    vector<pii> v;
    ll m1=MOD,m2=MOD;
    rep(i,n){
        ll a,b;
        cin>>a>>b;
        p[i].first=a;p[i].second=b;
        m2=min(m2,b);
        if(m2<m1) swap(m1,m2);
        v.pb(p[i]);
    }
    sort(v.begin(),v.end());
    ll num[N]={};
    ll sum=0;
    rep2(i,1,n){
        int l=lower_bound(v.begin(),v.end(),(pii){i,0})-v.begin();
        int r=lower_bound(v.begin(),v.end(),(pii){i+1,0})-v.begin();
        ll t=v[l].second;
        if(t!=m1){
            rep2(j,l,r-1){
                if((t+v[j].second<=x&&t+m1<=y)||v[j].second+m1<=y)
                num[i]++;
            }
        }
        else{
            rep2(j,l,r-1){
                if((t+v[j].second<=x&&t+m2<=y)||v[j].second+m2<=y)
                num[i]++;
            }
        }
        sum+=num[i];
    }
    calc_inv(n);
    ll ans=1;
    for(ll i=1;i<=sum;i++){
        ans=(ans*i)%MOD;
    }
    rep2(i,1,n){
        rep2(j,1,num[i]) ans=(ans*inv[j])%MOD;
    }
    cout<<(ans+MOD)%MOD;
    
}

Submission Info

Judge Result