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