| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1106246 |
2024-10-29T16:22:48 Z |
_rain_ |
Boat (APIO16_boat) |
C++14 |
|
506 ms |
4680 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
typedef pair<int,int> ii;
#define fi first
#define se second
#define name "main"
const int N=(int)500;
const int MOD=(int)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+MOD:a-b;
}
int mul(int a,int b){
return (ll)a*b%MOD;
}
int power(int a,int b){
int res=1;
for(;b;b>>=1,a=mul(a,a))
if (b&1) res=mul(res,a);
return res;
}
vector<int>nen;
vector<ii>line;
int a[N+2],b[N+2],n;
int L[N+2]={},R[N+2]={},f[N+2][2*N+2]={},dp[N+2][2*N+2]={};
int sing[N+2]={},fact[N+2]={},inv[N+2]={},w[N+2]={};
int Combine(int x,int y){
if (x>y) return 0;
return (ll)fact[y]*inv[y-x]%MOD*inv[x]%MOD;
}
int C(int k,int n){
if (k>n) return 0;
int res=1;
for(int i=n-k+1;i<=n;++i) res=mul(res,i);
return mul(res,inv[k]);
}
bool intersec(ii x,int a,int b){
if (b<x.fi||a>x.se) return false;
return true;
}
void build(){
memset(L,0x3f,sizeof L);
memset(R,-0x3f,sizeof R);
fact[0]=1;
for(int i=1;i<=N;++i) fact[i]=mul(fact[i-1],i);
inv[N]=power(fact[N],MOD-2);
for(int i=N;i>=1;--i) inv[i-1]=mul(inv[i],i);
for(int id=1;id<=line.size();++id){
int dodai=line[id-1].se-line[id-1].fi+1;
for(int j=1;j<=n;++j) w[j]=C(j,dodai);
for(int j=1;j<=n;++j){
for(int c=1;c<=j;++c)
f[id][j]=add(f[id][j],mul(Combine(c-1,j-1),w[c]));
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=line.size();++j){
if (intersec(line[j-1],a[i],b[i]))
L[i]=min(L[i],j),R[i]=max(R[i],j);
}
}
return;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i]>>b[i];
nen.push_back(a[i]);
nen.push_back(b[i]);
nen.push_back(a[i]-1);
}
sort(nen.begin(),nen.end());
nen.resize(unique(nen.begin(),nen.end())-nen.begin());
for(int i=1;i<nen.size();++i){
if (i-1==0) line.push_back({nen[i-1],nen[i]});
else line.push_back({nen[i-1]+1,nen[i]});
}
build();
for(int i=0;i<=line.size();++i) dp[0][i]=1;
for(int i=1;i<=n;++i){
// cout<<i<<'\n';
for(int id=L[i];id<=R[i];++id){
int cnt=0;
pair<int,int> xx=line[id-1];
if (id==L[i]){
int dodai=line[id-1].se-a[i]+1;
for(int j=0;j<=n;++j) sing[j]=0;
for(int j=1;j<=n;++j) w[j]=C(j,dodai);
for(int j=1;j<=n;++j){
for(int c=1;c<=j;++c)
sing[j]=add(sing[j],mul(Combine(c-1,j),w[c]));
}
xx={a[i],line[id-1].se};
}
for(int j=i;j>=1;--j){
if (intersec(xx,a[j],b[j])) ++cnt;
if (id==L[i]) dp[i][id]=add(dp[i][id],mul(sing[cnt],dp[j-1][id-1]));
else dp[i][id]=add(dp[i][id],mul(f[id][cnt],dp[j-1][id-1]));
}
}
for(int j=1;j<=line.size();++j) dp[i][j]=add(dp[i][j],dp[i][j-1]);
}
int ans=0;
for(int i=1;i<=n;++i) ans=add(ans,dp[i][line.size()]);
cout<<ans;
exit(0);
}
Compilation message
boat.cpp: In function 'void build()':
boat.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int id=1;id<=line.size();++id){
| ~~^~~~~~~~~~~~~
boat.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int j=1;j<=line.size();++j){
| ~^~~~~~~~~~~~~
boat.cpp: In function 'int32_t main()':
boat.cpp:85:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i=1;i<nen.size();++i){
| ~^~~~~~~~~~~
boat.cpp:90:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i=0;i<=line.size();++i) dp[0][i]=1;
| ~^~~~~~~~~~~~~
boat.cpp:112:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | for(int j=1;j<=line.size();++j) dp[i][j]=add(dp[i][j],dp[i][j-1]);
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
506 ms |
4680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
506 ms |
4680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
1924 KB |
Output is correct |
| 2 |
Correct |
20 ms |
1888 KB |
Output is correct |
| 3 |
Correct |
20 ms |
1872 KB |
Output is correct |
| 4 |
Correct |
20 ms |
1872 KB |
Output is correct |
| 5 |
Correct |
20 ms |
1872 KB |
Output is correct |
| 6 |
Correct |
21 ms |
1884 KB |
Output is correct |
| 7 |
Correct |
21 ms |
1872 KB |
Output is correct |
| 8 |
Correct |
21 ms |
1872 KB |
Output is correct |
| 9 |
Correct |
23 ms |
2040 KB |
Output is correct |
| 10 |
Correct |
20 ms |
2016 KB |
Output is correct |
| 11 |
Correct |
22 ms |
1872 KB |
Output is correct |
| 12 |
Correct |
19 ms |
1872 KB |
Output is correct |
| 13 |
Correct |
19 ms |
1872 KB |
Output is correct |
| 14 |
Correct |
19 ms |
1872 KB |
Output is correct |
| 15 |
Correct |
19 ms |
2000 KB |
Output is correct |
| 16 |
Correct |
11 ms |
1360 KB |
Output is correct |
| 17 |
Correct |
11 ms |
1360 KB |
Output is correct |
| 18 |
Correct |
11 ms |
1368 KB |
Output is correct |
| 19 |
Correct |
14 ms |
1296 KB |
Output is correct |
| 20 |
Correct |
12 ms |
1360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
506 ms |
4680 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
