Submission #975453

#TimeUsernameProblemLanguageResultExecution timeMemory
975453KenjikrabBoat (APIO16_boat)C++14
9 / 100
1683 ms8664 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; // } int choose(int n, int r) { if(r>n)return 0; // p holds the value of n*(n-1)*(n-2)..., // k holds the value of r*(r-1)... int p = 1, k = 1; // C(n, r) == C(n, n-r), // choosing the smaller value if (n - r < r) r = n - r; if (r != 0) { while (r) { p *= n; k *= r; // gcd of p, k int m = __gcd(p, k); // dividing by gcd, to simplify // product division by their gcd // saves from the overflow p /= m; k /= m; n--; r--; } // k should be simplified to 1 // as C(n, r) is a natural number // (denominator should be 1 ) . } else p = 1; return p; } 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; } 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]*choose(b+k-2,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:129:45: warning: unused variable 'c' [-Wunused-variable]
  129 |             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...