# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
203909 |
2020-02-23T01:59:32 Z |
Segtree |
Boat (APIO16_boat) |
C++14 |
|
2000 ms |
30456 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;
for(int i=1;i<N;i++){
mul(res,l);
mul(res,inv[i]);
if(i>l)res=0;
C[i][l]=res;
}
}
unordered_map<ll,ll> f[N];
void initf(ll l){
ll res=0;
for(int i=1;i<N;i++){
mad(res,C[i][l]);
f[i][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(xs[j+1]-xs[j],m)<<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;
xs.push_back(0); xs.push_back(1);
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();
}
for(int i=0;i<xs.size()-1;i++){
calcc(xs[i+1]-xs[i]);
initf(xs[i+1]-xs[i]);
}
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));
}
}
}
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:77: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:81:6:
rep(j,xs.size()-1){
~~~~~~~~~~~~~
boat.cpp:81: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:87:29:
for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
~~~~~~~~~~~~~
boat.cpp:87: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 |
Correct |
1092 ms |
30156 KB |
Output is correct |
2 |
Correct |
1120 ms |
30072 KB |
Output is correct |
3 |
Correct |
1124 ms |
30072 KB |
Output is correct |
4 |
Correct |
1158 ms |
30200 KB |
Output is correct |
5 |
Correct |
1168 ms |
30200 KB |
Output is correct |
6 |
Correct |
1350 ms |
30256 KB |
Output is correct |
7 |
Correct |
1368 ms |
30200 KB |
Output is correct |
8 |
Correct |
1396 ms |
30200 KB |
Output is correct |
9 |
Correct |
1386 ms |
30456 KB |
Output is correct |
10 |
Correct |
1406 ms |
30200 KB |
Output is correct |
11 |
Correct |
1369 ms |
30456 KB |
Output is correct |
12 |
Correct |
1447 ms |
30200 KB |
Output is correct |
13 |
Correct |
1409 ms |
30208 KB |
Output is correct |
14 |
Correct |
1682 ms |
30200 KB |
Output is correct |
15 |
Correct |
1468 ms |
30200 KB |
Output is correct |
16 |
Correct |
126 ms |
8056 KB |
Output is correct |
17 |
Correct |
167 ms |
8312 KB |
Output is correct |
18 |
Correct |
153 ms |
8184 KB |
Output is correct |
19 |
Correct |
126 ms |
8312 KB |
Output is correct |
20 |
Correct |
139 ms |
8312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1092 ms |
30156 KB |
Output is correct |
2 |
Correct |
1120 ms |
30072 KB |
Output is correct |
3 |
Correct |
1124 ms |
30072 KB |
Output is correct |
4 |
Correct |
1158 ms |
30200 KB |
Output is correct |
5 |
Correct |
1168 ms |
30200 KB |
Output is correct |
6 |
Correct |
1350 ms |
30256 KB |
Output is correct |
7 |
Correct |
1368 ms |
30200 KB |
Output is correct |
8 |
Correct |
1396 ms |
30200 KB |
Output is correct |
9 |
Correct |
1386 ms |
30456 KB |
Output is correct |
10 |
Correct |
1406 ms |
30200 KB |
Output is correct |
11 |
Correct |
1369 ms |
30456 KB |
Output is correct |
12 |
Correct |
1447 ms |
30200 KB |
Output is correct |
13 |
Correct |
1409 ms |
30208 KB |
Output is correct |
14 |
Correct |
1682 ms |
30200 KB |
Output is correct |
15 |
Correct |
1468 ms |
30200 KB |
Output is correct |
16 |
Correct |
126 ms |
8056 KB |
Output is correct |
17 |
Correct |
167 ms |
8312 KB |
Output is correct |
18 |
Correct |
153 ms |
8184 KB |
Output is correct |
19 |
Correct |
126 ms |
8312 KB |
Output is correct |
20 |
Correct |
139 ms |
8312 KB |
Output is correct |
21 |
Execution timed out |
2077 ms |
9336 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
722 ms |
11000 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1092 ms |
30156 KB |
Output is correct |
2 |
Correct |
1120 ms |
30072 KB |
Output is correct |
3 |
Correct |
1124 ms |
30072 KB |
Output is correct |
4 |
Correct |
1158 ms |
30200 KB |
Output is correct |
5 |
Correct |
1168 ms |
30200 KB |
Output is correct |
6 |
Correct |
1350 ms |
30256 KB |
Output is correct |
7 |
Correct |
1368 ms |
30200 KB |
Output is correct |
8 |
Correct |
1396 ms |
30200 KB |
Output is correct |
9 |
Correct |
1386 ms |
30456 KB |
Output is correct |
10 |
Correct |
1406 ms |
30200 KB |
Output is correct |
11 |
Correct |
1369 ms |
30456 KB |
Output is correct |
12 |
Correct |
1447 ms |
30200 KB |
Output is correct |
13 |
Correct |
1409 ms |
30208 KB |
Output is correct |
14 |
Correct |
1682 ms |
30200 KB |
Output is correct |
15 |
Correct |
1468 ms |
30200 KB |
Output is correct |
16 |
Correct |
126 ms |
8056 KB |
Output is correct |
17 |
Correct |
167 ms |
8312 KB |
Output is correct |
18 |
Correct |
153 ms |
8184 KB |
Output is correct |
19 |
Correct |
126 ms |
8312 KB |
Output is correct |
20 |
Correct |
139 ms |
8312 KB |
Output is correct |
21 |
Execution timed out |
2077 ms |
9336 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |