fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define x first
  6. #define y second
  7.  
  8. const int MOD = 1e9, maxn = 1e5;
  9.  
  10. vector<int> sum;
  11.  
  12. void merge_sort(vector<pair<int, int> > &to_sort, vector<int> &inv, vector<int> &res, int l, int r)
  13. {
  14.     if(r - l == 1)
  15.         return;
  16.     int m = (l + r) / 2;
  17.     merge_sort(to_sort, inv, res, l, m);
  18.     merge_sort(to_sort, inv, res, m, r);
  19.     vector<pair<int, int> > tmp;
  20.     tmp.reserve(r - l + 1);
  21.     int it1 = l, it2 = m;
  22.     int cnt = 0;
  23.     while(it1 < m || it2 < r)
  24.     {
  25.         if(it2 == r || (it1 != m && to_sort[it1] < to_sort[it2]))
  26.         {
  27.             tmp.push_back(to_sort[it1]);
  28.             cnt += inv[to_sort[it1].y];
  29.             if(cnt > MOD) cnt -= MOD;
  30.             it1++;
  31.         }
  32.         else
  33.         {
  34.             tmp.push_back(to_sort[it2]);
  35.             res[to_sort[it2].y] += cnt;
  36.             if(res[to_sort[it2].y] > MOD) res[to_sort[it2].y] -= MOD;
  37.             it2++;
  38.         }
  39.     }
  40.     for(int i = l; i < r; i++)
  41.         to_sort[i] = tmp[i - l];
  42.  
  43. }
  44.  
  45. int main()
  46. {
  47.     ios::sync_with_stdio(0);
  48.     cin.tie(0);
  49.     int n, k;
  50.     cin >> n >> k;
  51.     vector<pair<int, int> > a(n);
  52.     vector<int> b(maxn + 1, 1);
  53.     for(int i = 0; i < n; i++)
  54.         cin >> a[i].x, a[i].y = i;
  55.     reverse(a.begin(), a.end());
  56.     for(int i = 0; i < n; i++) a[i].y = i;
  57.     for(int i = 1; i < k; i++)
  58.     {
  59.         vector<pair<int, int> > ta(a);
  60.         vector<int> tb(maxn + 1, 0);
  61.         merge_sort(ta, b, tb, 0, n);
  62.         b = tb;
  63.     }
  64.     int cnt = 0;
  65.     for(int i = 0; i < n; i++)
  66.     {
  67.         cnt += b[i];
  68.         if(cnt > MOD) cnt -= MOD;
  69.     }
  70.     cout << cnt;
  71.     return 0;
  72. }
Runtime error #stdin #stdout #stderr 0s 3236KB
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/gXqU70
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!