Submission #1677891

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
#define w1 first
#define w2 second
#define ls (x<<1)
#define rs (x<<1|1)
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) ((x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=1ll*x*x%p)if(k&1)res=1ll*res*x%p;return res;}
const int maxn=1e5+5,inf=1e9+10,mod=1e9+7;
int totmin,totrest,X,Y,n;
int mini[maxn],ban[maxn],rest[maxn],c[maxn],w[maxn],mini2[maxn],mini3[maxn],mini4[maxn];
int fac[maxn],ifac[maxn];
int main(){
	read(n);
	fac[0]=1;rep(i,1,n)fac[i]=1ll*fac[i-1]*i%mod;
	rep(i,0,n)ifac[i]=power(fac[i],mod-2,mod);
	rep(i,1,n)mini[i]=inf;
	totmin=inf;
	read(X);read(Y);
	rep(i,1,n)read(c[i]),read(w[i]),mini[c[i]]=min(mini[c[i]],w[i]),totmin=min(totmin,w[i]);
	mini2[1]=inf;rep(i,2,n)mini2[i]=min(mini2[i-1],mini[i-1]);
	mini3[n]=inf;per(i,n-1,1)mini3[i]=min(mini3[i+1],mini[i+1]);
	rep(i,1,n)mini4[i]=min(mini2[i],mini3[i]);
	int cnt=n;
	rep(i,1,n)if(mini[i]+totmin>Y)ban[i]=1,cnt--;
	if(cnt<=1)return puts("1"),0;
	rep(i,1,n)if(!ban[c[i]]&&((w[i]+mini[c[i]]<=X)||(w[i]+mini4[c[i]]<=Y)))rest[c[i]]++,totrest++;
	int ans=fac[totrest];
	rep(i,1,n)ans=1ll*ans*ifac[rest[i]]%mod;
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result