fork download
copy 
  1. /*
  2.     Cred : SunnyYeahBoi
  3.     It's my last chance (⌐■_■)
  4.     Problem :
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12. #define double long double
  13. #define endl "\n"
  14. #define NAME "a"
  15.  
  16. const int MAXN = 1e5 + 5;
  17. const int inf = 1e18;
  18. const int MOD = 1e9;
  19.  
  20. void FileInput(){
  21.     if(fopen(NAME".inp" , "r") == NULL)
  22.         freopen(NAME".inp" , "w" , stdout);
  23.     freopen(NAME".inp" , "r" , stdin);
  24.     freopen(NAME".out" , "w" , stdout);
  25. }
  26.  
  27. const int MAXK = 15;
  28.  
  29. int n , k;
  30. int a[MAXN];
  31. int cnt[MAXN];
  32. int f[MAXN][MAXK];
  33.  
  34. struct Segtree{
  35.     vector<int> tree;
  36.     int n;
  37.  
  38.     void init(int x){
  39.         n = x + 1;
  40.         tree.resize(4 * n + 1 , 0);
  41.     }
  42.  
  43.     void update(int vt , int l , int r , int x , int y){
  44.         if(l == r){
  45.             tree[vt] += y;
  46.             tree[vt] %= MOD;
  47.             return;
  48.         }
  49.         int mid = (l + r) / 2;
  50.  
  51.         if(x <= mid)
  52.             update(vt * 2 , l , mid , x , y);
  53.         else update(vt * 2 + 1 , mid + 1 , r , x , y);
  54.  
  55.         tree[vt] = tree[vt * 2] + tree[vt * 2 + 1];
  56.     }
  57.  
  58.     void update(int x , int y){
  59.         update(1 , 1 , n , x , y);
  60.     }
  61.  
  62.     int get(int vt , int l , int r , int u , int v){
  63.         if(u <= l && r <= v)
  64.             return tree[vt];
  65.  
  66.         if(l > v || r < u)
  67.             return 0;
  68.  
  69.         int mid = (l + r) / 2;
  70.         return (get(vt * 2 , l , mid , u , v) + get(vt * 2 + 1 , mid + 1 , r , u , v)) % MOD;
  71.     }
  72.  
  73.     int get(int l , int r){
  74.         return get( 1 , 1 , n , l , r);
  75.     }
  76. } ST[MAXK];
  77.  
  78. void solve(){
  79.     cin >> n >> k;
  80.     for(int i = 1 ; i <= n ; i++)
  81.         cin >> a[i];
  82.  
  83.     map<int , int> mp;
  84.     for(int i = 1 ; i <= n ; i ++)
  85.         mp[a[i]]++;
  86.     mp[-inf];
  87.  
  88.     vector<int> nums;
  89.     for(auto x : mp)
  90.         nums.push_back(x.first);
  91.  
  92.     // for(auto x : nums)
  93.     //     cout << x << endl;
  94.  
  95.     for(int i = 1 ; i <= k ; i++)
  96.         ST[i].init(n);
  97.  
  98.     for(int i = 1 ; i <= n ; i++)
  99.         f[i][1] = 1;
  100.  
  101.     for(int j = 2 ; j <= k ; j++){
  102.         for(int i = 1 ; i <= n ; i++){
  103.             int id = lower_bound(nums.begin() , nums.end() , a[i]) - nums.begin();
  104.             f[i][j] = ST[j - 1].get(id + 1 , (int)nums.size() - 1) % MOD;
  105.             ST[j - 1].update(id , f[i][j - 1]);
  106.         }
  107.     }
  108.  
  109.     int res = 0;
  110.     for(int i = 1; i <= n ; i++)
  111.         res = (res + f[i][k]) % MOD;
  112.     cout << res << endl;
  113. }
  114.  
  115. int32_t main(){
  116.     //FileInput();
  117.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  118.     int t = 1;
  119.     // cin >> t;
  120.     while(t--)
  121.         solve();
  122.     return 0;
  123. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/2JH6R2
language:
C++14 (gcc 8.3)
created:
9 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!