fork(1) download
copy 
  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.  
  11. template<class Node_CItr,class Node_Itr,class Cmp_Fn,class _Alloc>
  12. struct my_update_policy
  13. {
  14.     virtual Node_CItr node_begin() const=0;
  15.     virtual Node_CItr node_end() const=0;
  16.     typedef int metadata_type;
  17.  
  18.     int get(int x)
  19.     {
  20.         auto it=node_begin();
  21.         while(it!=node_end())
  22.         {
  23.             auto l=it.get_l_child();
  24.             auto r=it.get_r_child();
  25.             int T=x+1;
  26.             if(l!=node_end()) T+=l.get_metadata();
  27.             if(T<=**it)
  28.             {
  29.                 it=l;
  30.             }
  31.             else
  32.             {
  33.                 x=T;
  34.                 it=r;
  35.             }
  36.         }
  37.         return x;
  38.     }
  39.  
  40.     void operator()(Node_Itr it, Node_CItr end_it)
  41.     {
  42.         auto l=it.get_l_child();
  43.         auto r=it.get_r_child();
  44.         int left=0,right=0;
  45.         if(l!=end_it) left=l.get_metadata();
  46.         if(r!=end_it) right=r.get_metadata();
  47.         const_cast<int&>(it.get_metadata())=left+right+1;
  48.     }
  49. };
  50.  
  51. tree<int,null_type,less<int>,rb_tree_tag,my_update_policy> me;
  52.  
  53. int main()
  54.  {
  55.     #ifndef ONLINE_JUDGE
  56.     freopen(TASK".in","r",stdin);
  57.     freopen(TASK".out","w",stdout);
  58.     #endif
  59.     ios::sync_with_stdio(0);
  60.     cin.tie(0);
  61.     int n,m;
  62.     cin>>n>>m;
  63.  
  64.     for(int i=0;i<m;i++)
  65.     {
  66.         char a;
  67.         int b;
  68.         cin>>a>>b;
  69.         if(a=='L')
  70.             cout<<me.get(b)<<"\n";
  71.         else
  72.             me.insert(me.get(b));
  73.     }
  74.  }
  75.  
Time limit exceeded #stdin #stdout 5s 63144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/stO6Xl
Timus 1439 O(nlogn)
language:
C++14 (gcc 8.3)
created:
9 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!