fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(x) (int)(x).size()
  8. #define FILL(a,b) memset(a,b,sizeof(a))
  9. using namespace std;
  10. typedef long long ll;
  11. typedef pair<int,int> ii;
  12. const int N = 1000003;
  13. const ll MOD = 1000000007LL;
  14.  
  15. struct BIT{
  16.     int n;
  17.     vector<ll> f;
  18.     void init(int m){ n=m; f.assign(n+5,0); }
  19.     void add(int i, ll v){ for(; i<=n; i+=i&-i){ f[i]+=v; if(f[i]>=MOD) f[i]-=MOD; } }
  20.     ll sum(int i){ ll s=0; for(; i>0; i-=i&-i){ s+=f[i]; if(s>=MOD) s-=MOD; } return s; }
  21. };
  22.  
  23. int main(){
  24.     ios::sync_with_stdio(false);
  25.     cin.tie(NULL);
  26.     cout.tie(NULL);
  27.  
  28.     int n;
  29.     if(!(cin>>n)) return 0;
  30.     vector<ll> a(n+1), b;
  31.     FOR(i,1,n){ cin>>a[i]; b.pb(a[i]); }
  32.     sort(b.begin(), b.end());
  33.     b.erase(unique(b.begin(), b.end()), b.end());
  34.     int m = sz(b);
  35.  
  36.     vector<ll> L(n+1,0), R(n+1,0);
  37.     BIT bit;
  38.     bit.init(m);
  39.     FOR(i,1,n){
  40.         int p = int(lower_bound(b.begin(), b.end(), a[i]) - b.begin()) + 1;
  41.         L[i] = (1 + bit.sum(p-1)) % MOD;
  42.         bit.add(p, L[i]);
  43.     }
  44.     bit.init(m);
  45.     for(int i=n;i>=1;--i){
  46.         int p = int(lower_bound(b.begin(), b.end(), a[i]) - b.begin()) + 1;
  47.         R[i] = (1 + bit.sum(p-1)) % MOD;
  48.         bit.add(p, R[i]);
  49.     }
  50.     ll ans = 1;
  51.     FOR(i,1,n){
  52.         ans = (ans + (L[i] * R[i]) % MOD) % MOD;
  53.     }
  54.     cout << ans;
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MKO9Bx
language:
C++14 (clang 8.0)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!