fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define ll long long
  6. #define ull unsigned long long
  7. #define pll pair<ll,ll>
  8. #define pb push_back
  9. #define emb emplace_back
  10. #define lg(x) __lg(x)
  11. #define all(s) s.begin(),s.end()
  12. #define name "test"
  13. #define Mask(i) (1LL<<i)
  14. #define testbit(mask, i) ((mask >> i) & 1LL)
  15. #define onBit(mask, i) (mask | (1LL << i))
  16. #define offBit(mask, i) (mask & ~(1LL << i))
  17. #define flipBit(mask, i) (mask ^ (1LL << i))
  18. #define showbit(mask, x) bitset<x>(mask)
  19. const ll mod = 1e9 + 7;
  20.  
  21. void add(ll &a, ll b){
  22.      if((a += b) >= mod) a -= mod;
  23. }
  24.  
  25.  
  26. const ll inf = 1e18;
  27. const ll lim = 1e7 + 5;
  28. const ll N = 1e5 + 5;
  29.  
  30. ll a[N];
  31. ll dp1[N], dp2[N];
  32.  
  33. ll bit[N];
  34. void update(int u, ll val){
  35.      for(int i = u; i < N; i += i & -i)
  36.           bit[i] = (bit[i] + val) % mod;
  37. }
  38. ll get(int u){
  39.      ll res = 0;
  40.      for(int i = u; i > 0; i -= i & -i)
  41.           res = (res + bit[i]) % mod;
  42.      return res;
  43. }
  44. int main()
  45. {
  46.      ios_base::sync_with_stdio(0);
  47.      cout.tie(0);cin.tie(0);
  48.      if(fopen(name".inp","r")){
  49.           freopen(name".inp","r",stdin);
  50.           freopen(name".out","w",stdout);
  51.      }
  52.  
  53.      int n, k; cin >> n >> k;
  54.      vector<int> zip;
  55.      for(int i = 1; i <= n; i++){
  56.           cin >> a[i];
  57.           zip.pb(a[i]);
  58.      }
  59.      sort(all(zip));
  60.      zip.erase(unique(all(zip)), zip.end());
  61.      for(int i = 1; i <= n; i++) a[i] = lower_bound(all(zip), a[i]) - zip.begin() + 1;
  62.  
  63.      for(int i = 1; i <= n; i++){
  64.           dp1[i] = 1;
  65.      }
  66.      for(int j = 2; j <= k; j++){
  67.           update(a[j - 1], dp1[j - 1]);
  68.           for(int i = j; i <= n; i++){
  69.                dp2[i] = get(a[i] - 1);
  70.                update(a[i], dp1[i]);
  71.           }
  72.           update(a[j - 1], -dp1[j - 1]);
  73.           for(int i = j; i <= n; i++){
  74.                update(a[i], -dp1[i]);
  75.                dp1[i] = dp2[i];
  76.           }
  77.      }
  78.      ll res = 0;
  79.      for(int i = k; i <= n; i++) res = (res + dp1[i]) % mod;
  80.      cout << res;
  81. }
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
32766
https://ideone.com/rijZWA
language:
C++14 (clang 8.0)
created:
3 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!