fork download
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #pragma pack(1)
  5.  
  6. using namespace std;
  7. using namespace __gnu_pbds;
  8.  
  9. #define TASK "test"
  10. #define int unsigned int
  11. const int MOD=1000000000;
  12.  
  13. template<class Node_CItr,class Node_Itr,class Cmp_Fn,class _Alloc>
  14. struct my_update_policy
  15. {
  16. virtual Node_CItr node_begin() const=0;
  17. virtual Node_CItr node_end() const=0;
  18. typedef int metadata_type;
  19.  
  20. int prefix_sum(int x)
  21. {
  22. int ans=0;
  23. auto it=node_begin();
  24. while(it!=node_end())
  25. {
  26. auto l=it.get_l_child();
  27. auto r=it.get_r_child();
  28. if(Cmp_Fn()(x,(*it)->first))
  29. {
  30. it=l;
  31. }
  32. else
  33. {
  34. ans+=(*it)->second;
  35. if(l!=node_end()) ans+=l.get_metadata();
  36. ans%=MOD;
  37. it=r;
  38. }
  39. }
  40. return ans;
  41. }
  42.  
  43. void operator()(Node_Itr it, Node_CItr end_it)
  44. {
  45. auto l=it.get_l_child();
  46. auto r=it.get_r_child();
  47. int left=0,right=0;
  48. if(l!=end_it) left=l.get_metadata();
  49. if(r!=end_it) right=r.get_metadata();
  50. const_cast<int&>(it.get_metadata())=(left+right+(*it)->second)%MOD;
  51. }
  52. };
  53.  
  54. tree<int,int,less<int>,rb_tree_tag,my_update_policy> me;
  55.  
  56. main()
  57. {
  58. #ifndef ONLINE_JUDGE
  59. freopen(TASK".in","r",stdin);
  60. freopen(TASK".out","w",stdout);
  61. #endif
  62. ios::sync_with_stdio(0);
  63. cin.tie(0);
  64. int n,k;
  65. cin>>n>>k;
  66. vector<int> a(n);
  67. for(auto &it:a) cin>>it;
  68. vector<int> inv(n,1);
  69. for(int i=1;i<k;i++)
  70. {
  71. me.clear();
  72. vector<int> t(n);
  73. int sum=0;
  74. for(int i=0;i<n;i++)
  75. {
  76. t[i]=sum-me.prefix_sum(a[i])+MOD;
  77. me.insert({a[i],inv[i]});
  78. sum+=inv[i];
  79. sum%=MOD;
  80. t[i]%=MOD;
  81. }
  82. swap(t,inv);
  83. }
  84. cout<<accumulate(inv.begin(),inv.end(),0ll)%MOD<<endl;
  85. }
Runtime error #stdin #stdout #stderr 3.63s 529920KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc