fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "icebear"
  33. /*END OF TEMPLATE. ICEBEAR AND THE CAT WILL WIN VOI26 */
  34.  
  35. const int MOD = 1e9 + 7;
  36. const int inf = 1e9 + 27092008;
  37. const ll INF = 1e18 + 27092008;
  38. const int N = 2e5 + 5;
  39. int n, a[N], ft[N];
  40. vector<int> compress;
  41.  
  42. void update(int x, int val) {
  43.     for(x++; x <= n + 1; x += x & -x) (ft[x] += val) %= MOD;
  44. }
  45.  
  46. int get(int x) {
  47.     int ans = 0;
  48.     for(x++; x; x -= x & -x) (ans += ft[x]) %= MOD;
  49.     return ans;
  50. }
  51.  
  52. void init(void) {
  53.     cin >> n;
  54.     FOR(i, 1, n) cin >> a[i], compress.pb(a[i]);
  55.     sort(all(compress));
  56.     compress.resize(unique(all(compress)) - compress.begin());
  57.     FOR(i, 1, n) a[i] = upper_bound(all(compress), a[i]) - compress.begin();
  58. }
  59.  
  60. void process(void) {
  61.     vector<int> f(n + 5, 0), g(n + 5, 0);
  62.     update(0, +1);
  63.     FOR(i, 1, n) {
  64.         f[i] = get(a[i] - 1);
  65.         update(a[i], f[i]);
  66.     }
  67.  
  68.     memset(ft, 0, sizeof ft);
  69.     update(0, +1);
  70.     FORR(i, n, 1) {
  71.         g[i] = get(a[i] - 1);
  72.         update(a[i], g[i]);
  73.     }
  74.  
  75.     int ans = 1;
  76.     FOR(i, 1, n) ans = (ans + 1LL * f[i] * g[i] % MOD) % MOD;
  77.     cout << ans;
  78. }
  79.  
  80. int main() {
  81.     ios_base::sync_with_stdio(0);
  82.     cin.tie(0); cout.tie(0);
  83.     if (fopen(task".inp", "r")) {
  84.         freopen(task".inp", "r", stdin);
  85.         freopen(task".out", "w", stdout);
  86.     }
  87.     int tc = 1;
  88. //    cin >> tc;
  89.     while(tc--) {
  90.         init();
  91.         process();
  92.     }
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/8iGzsW
language:
C++14 (gcc 8.3)
created:
11 hours 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!