| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 203915 |
2020-02-23T02:43:49 Z |
Segtree |
Boat (APIO16_boat) |
C++14 |
|
2000 ms |
29816 KB |
#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define mul(a,b) a=a*b%mod
#define N 510
ll po(ll x,ll y){
ll res=1;
for(;y;y>>=1){
if(y&1)mul(res,x);
x=x*x%mod;
}
return res;
}
ll inv[N];
unordered_map<ll,ll> C[N];
void calcc(ll l){
ll res=1;
C[0][l]=1;
for(ll i=1;i<N;i++){
mul(res,(l+1LL-i));
mul(res,inv[i]);
if(i>l)res=0;
C[i][l]=res;
}
}
unordered_map<ll,ll> f[N];
void initf(ll l,ll m){
ll res=0;
for(int i=1;i<=m;i++){
mad(res,C[i][l]*C[i-1][m-1]);
}
f[m][l]=res;
}
ll n,a[N],b[N];
ll rui[2*N][N];
vector<ll> xs;
ll edge(ll j,ll i,ll ii){
ll m=rui[j][ii]-rui[j][i];
/*for(int k=i;k<ii;k++){
if(a[k]<=j&&j<b[k])m++;
}*/
//cout<<"edge("<<j<<","<<i<<","<<ii<<")="<<f[m][xs[j+1]-xs[j]]<<endl;
//cout<<"l="<<xs[j+1]-xs[j]<<", m="<<m<<endl;
return f[m][xs[j+1]-xs[j]];
}
ll dp[N][2*N];
int main(){
for(int i=1;i<N;i++)inv[i]=po(i,mod-2);
cin>>n;
a[0]=b[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
a[n+1]=2e9,b[n+1]=2e9;
for(int i=0;i<=n+1;i++){
b[i]++;
xs.push_back(a[i]);
xs.push_back(b[i]);
}
sort(all(xs));
xs.erase(unique(all(xs)),xs.end());
for(int i=0;i<=n+1;i++){
a[i]=lower_bound(all(xs),a[i])-xs.begin();
b[i]=lower_bound(all(xs),b[i])-xs.begin();
}
rep(i,N)calcc(i);
for(int i=0;i<xs.size()-1;i++){
calcc(xs[i+1]-xs[i]);
for(int m=1;m<N;m++)initf(xs[i+1]-xs[i],m);
}
rep(j,xs.size()-1){
rui[j][0]=0;
for(int i=0;i<=n+1;i++){
rui[j][i+1]=rui[j][i]+(a[i]<=j&&j<b[i]);
}
}
for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
dp[0][0]=1;
for(int ii=1;ii<=n+1;ii++){
for(int jj=a[ii];jj<b[ii];jj++){
for(int i=0;i<ii;i++)for(int j=0;j<jj;j++){
mad(dp[ii][jj],dp[i][j]*edge(j,i,ii));
}
//cout<<"dp["<<ii<<"]["<<jj<<"]="<<dp[ii][jj]<<endl;
}
}
ll ans=dp[n+1][a[n+1]]+mod-1; ans%=mod;
cout<<ans<<endl;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<xs.size()-1;i++){
~^~~~~~~~~~~~
boat.cpp:10:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,n) for(int i=0;i<n;i++)
boat.cpp:82:6:
rep(j,xs.size()-1){
~~~~~~~~~~~~~
boat.cpp:82:2: note: in expansion of macro 'rep'
rep(j,xs.size()-1){
^~~
boat.cpp:10:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,n) for(int i=0;i<n;i++)
boat.cpp:88:29:
for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
~~~~~~~~~~~~~
boat.cpp:88:25: note: in expansion of macro 'rep'
for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2099 ms |
29816 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2099 ms |
29816 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1398 ms |
24060 KB |
Output is correct |
| 2 |
Correct |
1306 ms |
24044 KB |
Output is correct |
| 3 |
Correct |
1353 ms |
24056 KB |
Output is correct |
| 4 |
Correct |
1410 ms |
24056 KB |
Output is correct |
| 5 |
Correct |
1463 ms |
24212 KB |
Output is correct |
| 6 |
Correct |
1961 ms |
24056 KB |
Output is correct |
| 7 |
Execution timed out |
2037 ms |
24312 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2099 ms |
29816 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
