Submission #975479

#TimeUsernameProblemLanguageResultExecution timeMemory
975479KenjikrabBoat (APIO16_boat)C++14
100 / 100
227 ms12888 KiB
#include<bits/stdc++.h> #define int long long #define pii pair<int,int> #define fi first #define se second using namespace std; int const mod=1e9+7; map<int,int> ind; vector<int> val; vector<int> fen(1010,0); void upd(int idx,int val) { idx+=2; for(int i=idx;i<1010;i+=i&-i)fen[i]+=val,fen[i]%=mod; } int qr(int idx) { idx+=2; int ret=0; for(int i=idx;i>0;i-=i&-i)ret+=fen[i],ret%=mod; return ret; } int pow(int a,int b) { if(b==0)return 1; if(b==1)return a; int ret=pow(a,b/2); if(b%2==0)return (ret*ret)%mod; else return (((ret*ret)%mod)*a)%mod; } vector<int> inverse(510); void inv(int a) { inverse[a]=pow(a,mod-2); } int invfac[1010]; int cycle=1; vector<vector<int>> keep1(1010,vector<int>(510,0)); int choose1(int a,int b) { if(b>a)return 0; if(a==b)return 1; if(a-b>b)b=a-b; int ret=1; for(int i=b+1;i<=a;i++) { ret*=i; ret%=mod; } ret*=invfac[a-b]; ret%=mod; return ret; } int choose(int a,int b) { int ret=keep1[a][b]; ret*=invfac[b]; ret%=mod; //cout<<a<<"-"<<b<<" "<<ret<<endl; return ret; } signed main() { cin.tie(nullptr)->sync_with_stdio(false); for(int i=2;i<510;i++)inv(i); invfac[0]=1; invfac[1]=1; for(int i=2;i<510;i++)invfac[i]=invfac[i-1]*inverse[i],invfac[i]%=mod; int n; cin>>n; vector<pii> info; set<int> temp; for(int i=0;i<n;i++) { int a,b; cin>>a>>b; temp.insert(a); temp.insert(b+1); info.push_back({a,b+1}); } for(auto it:temp) { val.push_back(it); ind[it]=val.size()-1; } for(int i=0;i<val.size()-1;i++) { int a=val[i+1]-val[i]-1; keep1[i][0]=1; for(int j=1;j<510;j++) { keep1[i][j]=(keep1[i][j-1]*a)%mod; a++; } } vector<vector<int>> pre(510,vector<int>(1010,-2)); vector<int> latest(1010,-1); upd(-1,1); vector<vector<int>> dp(510,vector<int>(1010,0)); for(int i=0;i<n;i++) { //cout<<endl<<i<<":"; for(int j=ind[info[i].se]-1;j>=ind[info[i].fi];j--) { //cout<<j<<" "; int bef=latest[j]; pre[i][j]=latest[j]; latest[j]=i; int a=qr(j),b=(val[j+1]-val[j]),c=0; dp[i][j]=a; int ans=a*b; ans%=mod; int k=2; //cout<<i<<" "<<j<<" "<<ans<<" "; while(bef!=-1) { ans+=dp[bef][j]*((b+k-2<k)?0:choose(j,k)); ans%=mod; bef=pre[bef][j]; k++; //cout<<endl<<bef<<" "<<ans<<" "; } // cout<<endl; upd(j+1,ans); } } cout<<(qr(1007)+mod-1)%mod; return 0; }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:87:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<val.size()-1;i++)
      |                 ~^~~~~~~~~~~~~
boat.cpp:111:45: warning: unused variable 'c' [-Wunused-variable]
  111 |             int a=qr(j),b=(val[j+1]-val[j]),c=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...