Submission #1106058

#TimeUsernameProblemLanguageResultExecution timeMemory
1106058_rain_Boat (APIO16_boat)C++14
0 / 100
306 ms4304 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...