fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MOD = 1e9;
  6.  
  7. vector<int> sum;
  8.  
  9. void add(int pos, int k)
  10. {
  11.     for(; pos < sum.size(); pos |= pos + 1)
  12.         sum[pos] = (sum[pos] + k) % MOD;
  13. }
  14.  
  15. int get(int pos)
  16. {
  17.     int ret = 0;
  18.     for(; pos > 0; pos = (pos & (pos + 1)) - 1)
  19.         ret = (ret + sum[pos]) % MOD;
  20.     return ret;
  21. }
  22.  
  23. int main()
  24. {
  25.     int n, k;
  26.     cin >> n >> k;
  27.     vector<int> a(n), b(n, 1);
  28.     for(int i = 0; i < n; i++)
  29.         cin >> a[i];
  30.     for(int i = 0; i < k; i++)
  31.     {
  32.         sum.assign(n + 1, 0);
  33.         for(int j = n - 1; j >= 0; j--)
  34.         {
  35.             add(a[j], b[j]);
  36.             b[j] = get(a[j] - 1);
  37.         }
  38.     }
  39.     cout << get(n);
  40.     return 0;
  41. }
Runtime error #stdin #stdout #stderr 0s 3428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/qxT0jJ
language:
C++14 (gcc 8.3)
created:
8 years 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!