fork download
copy 
  1. // SIGMA BOY hihihihihihihi
  2.  
  3. #define se second
  4. #define fi first
  5. #define pb push_back
  6. #define pob pop_back
  7. #define bitebi __builtin_popcountll
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std ;
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef pair<ll,ll> pll;
  14.  
  15. const ll Mod = 1e9+7;
  16. const ll Maxn = 1e5+69;
  17. const ll oo = 1e18;
  18. const int inf = 1e9;
  19.  
  20. ll n , k , a[Maxn], dp[Maxn][12] , st[5*Maxn][12];
  21.  
  22. void Update ( int id , int l , int r , int k_cur , int v , ll ins)
  23. {
  24.     if(r<v||l>v) return;
  25.     if(l==r)
  26.     {
  27.         st[id][k_cur]+=ins;
  28.         return;
  29.     }
  30.     int mid = (l+r)/2;
  31.     Update(id*2,l,mid,k_cur,v,ins);
  32.     Update(id*2+1,mid+1,r,k_cur,v,ins);
  33.     st[id][k_cur] = st[id*2][k_cur] + st[id*2+1][k_cur];
  34. }
  35.  
  36. ll Get ( int id , int l , int r , int k_cur , int u , int v )
  37. {
  38.     if(v<l||r<u) return 0;
  39.     if(u<=l&&r<=v) return st[id][k_cur];
  40.     int mid = (l+r)/2;
  41.     return Get(id*2,l,mid,k_cur,u,v)
  42.             +Get(id*2+1,mid+1,r,k_cur,u,v);
  43. }
  44.  
  45. void Do()
  46. {
  47.     cin >> n >> k ;
  48.     for (int i = 1 ; i <= n ; ++i) cin >> a[i];
  49.     Update(1,0,n,0,0,1);
  50.     for (int i = 1 ; i <= n ; ++i)
  51.     {
  52.         for (int len = 1 ; len <= k+1 ; ++len)
  53.         {
  54.             dp[i][len] = Get(1,0,n,len-1,0,a[i]-1);
  55.             Update(1,0,n,len,a[i],dp[i][len]);
  56.         }
  57.     }
  58.     ll sum = 0 ;
  59.     for (int i = 1 ; i <= n ; ++i) sum+=dp[i][k+1];
  60.     cout << sum;
  61. }
  62.  
  63. signed main ()
  64. {
  65.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  66. #define task "test"
  67.     if(fopen(task".inp", "r")){
  68.         freopen(task".inp", "r", stdin);
  69.         freopen(task".out", "w", stdout);
  70.     }
  71.     int ntest=1;
  72.     while(ntest--) Do();
  73.  
  74.     cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
  75. }
  76.  
Success #stdin #stdout #stderr 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed: 5ms
https://ideone.com/704XAM
language:
C++14 (gcc 8.3)
created:
10 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!