Submission #2834977

---

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],comb[N];
void calc_inv(ll n){
    inv[1]=1;
    rep2(i,2,n){
        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 m=MOD;
    rep(i,n){
        ll a,b;
        cin>>a>>b;
        p[i].first=a;p[i].second=b;
        m=min(m,b);
        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;
        rep2(j,l,r-1){
            if((t+v[j].second<=x&&t+m<=y)||v[j].second+m<=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;
    
}

Submission Info

Judge Result