Submission #203916

#TimeUsernameProblemLanguageResultExecution timeMemory
203916SegtreeBoat (APIO16_boat)C++14
27 / 100
2086 ms30136 KiB
#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]; 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++){ if(jj>a[ii])mad(dp[ii][jj],dp[ii][jj-1]); for(int i=0;i<ii;i++)for(int j=(jj==a[ii]?0:jj-1);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 (stderr)

boat.cpp: In function 'int main()':
boat.cpp:73: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:77:6:
  rep(j,xs.size()-1){
      ~~~~~~~~~~~~~             
boat.cpp:77: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:83:29:
  for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
                             ~~~~~~~~~~~~~
boat.cpp:83: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...