| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1106058 |
2024-10-29T05:36:34 Z |
_rain_ |
Boat (APIO16_boat) |
C++14 |
|
306 ms |
4304 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 inv[N+2]={};
int L[N+2]={},R[N+2]={},f[N+2][2*N+2]={},dp[N+2][2*N+2]={};
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);
int tich=1;
inv[0]=power(tich,MOD-2);
for(int i=1;i<=N;++i) {
tich=mul(tich,i);
inv[i]=power(tich,MOD-2);
}
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){
f[id][j]=add(f[id][j-1],C(j,dodai));
}
}
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]);
}
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){
for(int id=L[i];id<=R[i];++id){
int cnt=0;
for(int j=i;j>=1;--j){
if (intersec(line[id-1],a[j],b[j])) ++cnt;
dp[i][id]=add(dp[i][id],mul(f[id][cnt],dp[j-1][id-1]));
}
}
for(int j=0;j<=line.size();++j) dp[i][j]=add(dp[i][j],dp[i-1][j]);
//for(int id=L[i];id<=R[i];++id) cout<<line[id-1].fi<<' '<<line[id-1].se<<'\n';
}
int ans=0;
for(int i=0;i<line.size();++i) ans=add(ans,sub(dp[n][i],1));
cout<<ans;
exit(0);
}
Compilation message
boat.cpp: In function 'void build()':
boat.cpp:53: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]
53 | for(int id=1;id<=line.size();++id){
| ~~^~~~~~~~~~~~~
boat.cpp:60: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]
60 | for(int j=1;j<=line.size();++j){
| ~^~~~~~~~~~~~~
boat.cpp: In function 'int32_t main()':
boat.cpp:79:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i=1;i<nen.size();++i){
| ~^~~~~~~~~~~
boat.cpp:84: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]
84 | for(int i=0;i<=line.size();++i) dp[0][i]=1;
| ~^~~~~~~~~~~~~
boat.cpp:93: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]
93 | for(int j=0;j<=line.size();++j) dp[i][j]=add(dp[i][j],dp[i-1][j]);
| ~^~~~~~~~~~~~~
boat.cpp:97: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]
97 | for(int i=0;i<line.size();++i) ans=add(ans,sub(dp[n][i],1));
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
4304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
4304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
1616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
4304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
