#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=502;
const int mod=1e9+7;
int used[N],sum[N],dp[N],ndp[N],choose[N],rev[N];
vector<pair<int,int> > ope;
int binpow(int x,int y){
int tich=1;
while(y){
if(y&1){
tich*=x;
tich%=mod;
}
x*=x;
x%=mod;
y>>=1;
}
return tich;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,i,j,k,l;
cin>>n;
for(i=1;i<=n;i++){
cin>>j>>k;
k++;
ope.push_back({j,i});
ope.push_back({k,i});
}
sort(ope.begin(),ope.end());
i=0;
j=0;
rev[0]=1;
for(i=1;i<=n;i++){
rev[i]=binpow(i,mod-2);
}
while(i<ope.size()){
while(j<ope.size()&&ope[j].first==ope[i].first){
used[ope[j].second]^=1;
j++;
}
for(k=1;k<=n;k++){
sum[k]=sum[k-1]+used[k];
}
if(j==ope.size()){
break;
}
int len=ope[j].first-ope[i].first,val=sum[n],c1=1,c2=1;
for(k=1;k<=min(len,val);k++){
c1=1;
c2=1;
choose[k]=0;
for(l=0;l<k;l++){
choose[k]+=c1*c2;
choose[k]%=mod;
c1=c1*(len-l);
c1%=mod;
c1=c1*rev[l+1];
c1%=mod;
c2=c2*(val-l);
c2%=mod;
c2=c2*rev[l+1];
c2%=mod;
}
}
ndp[0]=1;
for(k=1;k<=n;k++){
for(l=0;l<k;l++){
ndp[k]+=dp[l]*choose[sum[k]-sum[l]];
ndp[k]%=mod;
}
}
for(k=0;k<=n;k++){
dp[k]=ndp[k];
}
i=j;
}
int ans=0;
for(i=1;i<=n;i++){
ans+=dp[i];
if(ans>=mod){
ans-=mod;
}
}
cout<<ans;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:39:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i<ope.size()){
~^~~~~~~~~~~
boat.cpp:40:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j<ope.size()&&ope[j].first==ope[i].first){
~^~~~~~~~~~~
boat.cpp:47:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j==ope.size()){
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
668 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
668 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
668 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
