fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. #define int long long
  5. #define F(i, l, r) for(int i = l; i <= r; ++i)
  6. #define E(i, l, r) for(int i = l; i >= r; --i)
  7. #define eb emplace_back
  8. const ll mod = 1e9 + 7;
  9. const int ars = 2e5 + 5;
  10. const int ii = 1e9;
  11. const ll il = 1e18;
  12.  
  13. int n, id, bit[ars], a[ars];
  14.  
  15. void upd(int p, int x) {
  16.     for(; p <= id; p += p & -p) {
  17.         bit[p] += x;
  18.         bit[p] %= mod;
  19.     }
  20. }
  21.  
  22. int get(int p) {
  23.     int res = 0;
  24.     for(; p > 0; p -= p & -p) {
  25.         res += bit[p];
  26.         res %= mod;
  27.     }
  28.     return res;
  29. }
  30.  
  31. vector<int> vals;
  32. void compress() {
  33.     F(i, 1, n) {
  34.         vals.eb(a[i]);
  35.     }
  36.     sort(vals.begin(), vals.end());
  37.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  38.  
  39.     F(i, 1, n) {
  40.         a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
  41.     }
  42.     id = vals.size();
  43. }
  44.  
  45. int f[ars];
  46. void solve() {
  47.     cin >> n;
  48.     F(i, 1, n) cin >> a[i];
  49.     compress();
  50.     int res = 0;
  51.     F(i, 1, n) {
  52.         f[i] = get(a[i] - 1) + 1;
  53.         f[i] %= mod;
  54.         upd(a[i], f[i]);
  55.         res = (res + f[i]) % mod;
  56.     }
  57.     cout << res;
  58.  
  59. }
  60. signed main() {
  61.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  62.     int t = 1;
  63.     // cin >> t;
  64.     while(t--) solve();
  65.  
  66.  
  67.     return 0;
  68. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RTYEJd
language:
C++14 (gcc 8.3)
created:
11 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!