#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int mod = 1e9 + 7;
int add(int a,int b){
return (a + b >= mod ? a + b - mod : a + b);
}
int sub(int a,int b){
return (a - b >= 0 ? a - b : a - b + mod);
}
int mult(ll a,ll b){
return (a*b)%mod;
}
int power(int a,int b){
if(b == 0) return 1;
if(b == 1) return a;
int r = power(a,b/2);
if(b&1) return mult(mult(r,r),a);
return mult(r,r);
}
int divide(int a,int b){
return mult(a , power(b,mod-2));
}
int dp[2][505];
void solve(){
int n;
cin>>n;
vector<int> a(n),b(n);
vector<int> v;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
v.push_back(a[i]);
v.push_back(b[i]+1);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()) , v.end());
int new_n = v.size();
vector<vector<int>> idx(new_n+1);
for(int i=0;i<n;i++){
int l = lower_bound(v.begin(),v.end(),a[i]) - v.begin();
int r = upper_bound(v.begin(),v.end(),b[i]) - v.begin();
for(int j=l;j<r;j++){
idx[j].push_back(i+1);
}
}
vector<int> inv(n+1);
for(int i=1;i<=n;i++) inv[i] = divide(1,i);
for(int i=1;i<=n;i++) dp[new_n&1][i] = 1;
for(int j=new_n-1;j>=0;j--){
int sz = idx[j].size();
int dp2[2][sz+1]{};
for(int i=sz-1;i>=0;i--){
for(int k=1;k<=sz;k++){
if(k == 1) dp2[i&1][k] = add(dp2[i&1][k] , dp[j+1&1][idx[j][i]]);
else dp2[i&1][k] = add(dp2[i&1][k] , dp2[i+1&1][k-1]);
dp2[i&1][k] = add(dp2[i&1][k] , dp2[i+1&1][k]);
}
}
for(int i=0;i<=n;i++){
int gap = (j < new_n - 1 ? v[j+1] - v[j] : 0);
sz = min(sz , gap);
int x = 1;
int st = upper_bound(idx[j].begin(),idx[j].end(),i) - idx[j].begin();
dp[j&1][i] = dp[j+1&1][i];
for(int k=1;k<=sz;k++){
x = mult(x , gap-k+1);
x = mult(x , inv[k]);
dp[j&1][i] = add(dp[j&1][i],mult(dp2[st][k],x));
}
}
}
cout<<dp[0][0]<<endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
Compilation message
boat.cpp: In function 'void solve()':
boat.cpp:55:64: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
55 | if(k == 1) dp2[i&1][k] = add(dp2[i&1][k] , dp[j+1&1][idx[j][i]]);
| ~^~
boat.cpp:56:59: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
56 | else dp2[i&1][k] = add(dp2[i&1][k] , dp2[i+1&1][k-1]);
| ~^~
boat.cpp:57:54: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
57 | dp2[i&1][k] = add(dp2[i&1][k] , dp2[i+1&1][k]);
| ~^~
boat.cpp:65:30: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
65 | dp[j&1][i] = dp[j+1&1][i];
| ~^~
during RTL pass: expand
boat.cpp:52:13: internal compiler error: in make_decl_rtl, at varasm.c:1342
52 | int dp2[2][sz+1]{};
| ^~~
Please submit a full bug report,
with preprocessed source if appropriate.
See <file:///usr/share/doc/gcc-10/README.Bugs> for instructions.
