fork(19) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int mod = 5e6, maxn = 1e5;
  6.  
  7. int sum[maxn + 1], a[maxn], b[maxn];
  8.  
  9. void add(int i, int k)
  10. {
  11.     for(; i <= maxn; i += i & -i)
  12.     {
  13.         sum[i] += k;
  14.         if(sum[i] > mod) sum[i] -= mod;
  15.     }
  16. }
  17.  
  18. int get(int i)
  19. {
  20.     int ret = 0;
  21.     for(; i; i -= i & -i)
  22.     {
  23.         ret += sum[i];
  24.         if(ret > mod) ret -= mod;
  25.     }
  26.     return ret;
  27. }
  28.  
  29. int main()
  30. {
  31.     int n, k;
  32.     cin >> n >> k;
  33.     for(int i = 0; i < n; i++)
  34.         cin >> a[i], a[i]++, b[i] = 1;
  35.     for(int i = 0; i < k; i++)
  36.     {
  37.         memset(sum, 0, sizeof(sum));
  38.         for(int j = 0; j < n; j++)
  39.         {
  40.             add(a[j], b[j]);
  41.             b[j] = get(a[j] - 1);
  42.         }
  43.     }
  44.     cout << get(maxn) << "\n";
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0s 4516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/d3HGAB
increasing seq, BIT
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!