This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int,int>
#define fi first
#define se second
const int mod=(int)1e9+7;
const int maxn=2*505;
int sz,a[maxn],b[maxn];
vector<int>v,s;
int n;
vector<pll>block;
int val[maxn][maxn];
int cnt[maxn];
int add[maxn];
int chia[maxn];
int pw(int x,int y)
{
if(y==0) return 1;
int x1=pw(x,y/2);
x1=x1*x1%mod;
if(y&1) x1=x1*x%mod;
return x1;
}
int pre[maxn];
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i=1; i<=n; i++)
{
cin >> a[i] >> b[i];
v.push_back(a[i]-1);
v.push_back(b[i]);
}
for(int i=1;i<=n;i++) chia[i]=pw(i,mod-2);
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++)
{
if(i==0||v[i]!=v[i-1]) s.push_back(v[i]);
}
swap(v,s);
for(int i=0;i<v.size();i++)
{
if(i==0) block.push_back({0,v[i]});
else block.push_back({v[i-1]+1,v[i]});
}
for(int i=0;i<block.size();i++) pre[i]=1;
int tt=0,valcu;
for(int i=1;i<=n;i++)
{
a[i]=lower_bound(block.begin(),block.end(),(pll){a[i]+1,0ll})-block.begin()-1;
b[i]=lower_bound(block.begin(),block.end(),(pll){b[i]+1,0ll})-block.begin()-1;
//cout << a[i] <<' '<<b[i]<<'\n';
for(int j=a[i];j<=b[i];j++)
{
cnt[j]++;
val[j][cnt[j]]=pre[j-1];
for(int k=1;k<=cnt[j];k++)
{
tt=cnt[j]-k+1;
valcu=val[j][k]*(block[j].se-block[j].fi)%mod*chia[tt]%mod;
if(j==cnt[j]) valcu=0;
val[j][k]+=valcu;
if(val[j][k]>=mod) val[j][k]-=mod;
add[j]+=valcu;
if(add[j]>=mod) add[j]-=mod;
}
add[j]+=val[j][cnt[j]];
if(add[j]>=mod) add[j]-=mod;
}
for(int j=1;j<block.size();j++)
{
add[j]+=add[j-1];
pre[j]+=add[j];
if(pre[j]>=mod) pre[j]-=mod;
}
for(int j=1;j<block.size();j++) add[j]=0;
}
cout << (pre[block.size()-1]-1+mod)%mod;
}
Compilation message (stderr)
boat.cpp: In function 'int main()':
boat.cpp:40:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
boat.cpp:45:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
boat.cpp:50:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0;i<block.size();i++) pre[i]=1;
| ~^~~~~~~~~~~~~
boat.cpp:74:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int j=1;j<block.size();j++)
| ~^~~~~~~~~~~~~
boat.cpp:80:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int j=1;j<block.size();j++) add[j]=0;
| ~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |