Submission #974923

#TimeUsernameProblemLanguageResultExecution timeMemory
974923KenjikrabBoat (APIO16_boat)C++14
9 / 100
2058 ms198128 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; } map<int,int> inverse; int inv(int a) { if(inverse[a]!=0)return inverse[a]; inverse[a]=pow(a,mod-2); return inverse[a]; } int choose(int a,int b) { if(b>a)return 0; int ret=1; for(int i=b+1;i<=a;i++) { ret*=i; ret%=mod; } for(int i=2;i<=a-b;i++) { ret*=inv(i); ret%=mod; } return ret; } signed main() { 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; //cout<<it<<" "<<ind[it]<<endl; } vector<vector<int>> pre(510,vector<int>(1010,-2)); vector<int> latest(1010,-1); for(int i=0;i<n;i++) { for(int j=ind[info[i].fi];j<ind[info[i].se];j++) { pre[i][j]=latest[j]; latest[j]=i; } } 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 a=qr(j),b=(val[j+1]-val[j]); dp[i][j]=a; int ans=a*b; ans%=mod; int bef=pre[i][j],k=2; //cout<<i<<" "<<j<<" "<<ans<<" "; while(bef!=-1) { int sum=0; for(int l=k;l>=2;l--)sum+=choose(b,l)*choose(k-2,l-2),sum%=mod; ans+=dp[bef][j]*sum; ans%=mod; bef=pre[bef][j]; k++; //cout<<ans<<" "; } upd(j+1,ans); //cout<<endl; } } cout<<(qr(1007)+mod-1)%mod; return 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...