fork download 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct vertex
  6. {
  7.     vertex *left,*right;
  8.     short num;
  9. };
  10.  
  11. struct sg_tree
  12. {
  13.     static const int MPOW=31;
  14.     static const int N=1ll<<MPOW-1;
  15.     vertex arr[180000];
  16.     int sz;
  17.  
  18.     sg_tree():sz(1)
  19.     {
  20.         arr[0].left=0;
  21.         arr[0].right=0;
  22.         arr[0].num=0;
  23.     }
  24.  
  25.     void add(vertex *c,int cl,int cr,int x)
  26.     {
  27.         if(cl==cr)
  28.             c->num=1;
  29.         else
  30.         {
  31.             int cm=(cl+cr)>>1;
  32.             if(x<=cm)
  33.             {
  34.                 if(c->left==0)
  35.                 {
  36.                     c->left=arr+sz;
  37.                     arr[sz].right=0;
  38.                     arr[sz].left=0;
  39.                     sz++;
  40.                 }
  41.                 add(c->left,cl,cm,x);
  42.             }
  43.             else
  44.             {
  45.                 if(c->right==0)
  46.                 {
  47.                     c->right=arr+sz;
  48.                     arr[sz].right=0;
  49.                     arr[sz].left=0;
  50.                     sz++;
  51.                 }
  52.                 add(c->right,cm+1,cr,x);
  53.  
  54.             }
  55.             c->num=0;
  56.             if(c->left!=0)
  57.                 c->num+=c->left->num;
  58.             if(c->right!=0)
  59.                 c->num+=c->right->num;
  60.         }
  61.     }
  62.  
  63.     void add(int x)
  64.     {
  65.         add(arr,0,N-1,x);
  66.     }
  67.  
  68.     int sum(vertex *c,int cl,int cr,int x,int left)
  69.     {
  70.         if(cl==cr)
  71.             return cl;
  72.         int cm=(cl+cr)>>1;
  73.         int sum_l,sum_r;
  74.         if(c->left==0)
  75.         {
  76.             sum_l=0;
  77.             if(cm-left-sum_l>=x)
  78.                 return x+left;
  79.  
  80.         }
  81.         else
  82.         sum_l=c->left->num;
  83.         if(c->right==0 && cm-left-sum_l<x)
  84.             return x+left+sum_l;
  85.         if(cm-left-sum_l<x)
  86.             return sum(c->right,cm+1,cr,x,left+sum_l);
  87.         else
  88.             return sum(c->left,cl,cm,x,left);
  89.     }
  90.  
  91.     int get(int x)
  92.     {
  93.        return sum(arr,0,N-1,x,0);
  94.     }
  95. };
  96.  
  97. sg_tree rooms;
  98. main()
  99.  {
  100.     ios::sync_with_stdio(0);
  101.     cin.tie(0);
  102.     int n,m;
  103.     cin>>n>>m;
  104.     char t;
  105.     int r;
  106.     for(int i=0;i<m;i++)
  107.     {
  108.         cin>>t>>r;
  109.         if(t=='L')
  110.             cout<<rooms.get(r)<<"\n";
  111.         else
  112.             rooms.add(rooms.get(r));
  113.     }
  114. }
Success #stdin #stdout 0s 5600KB
comments (?)
stdin 
20 7
L 5
D 5
L 4
L 5
D 5
L 4
L 5
stdout 
5
4
6
4
7
https://ideone.com/uihDVe
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!