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
comments (?)
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
https://ideone.com/dqYqcY
Timus 1523 O(knlogn)
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!