Saleh127

Light OJ 1087 / Segment tree

Oct 24th, 2021
627
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2.  created: 2021-10-24-14.33.35
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long
  8. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  9. #define get_lost_idiot return 0
  10. #define siz 200005
  11. ll a[200005],f[siz];
  12. ll tree[800005];
  13.  
  14. void treeconstruct(ll node,ll b,ll e)
  15. {
  16.  
  17.     if(b==e)
  18.     {
  19.         if(a[b]) tree[node]=1;
  20.         else tree[node]=0;
  21.         return;
  22.     }
  23.  
  24.     ll left = node*2;
  25.     ll right = node*2 + 1ll;
  26.  
  27.     ll mid=(b+e)/2;
  28.  
  29.     treeconstruct(left,b,mid);
  30.     treeconstruct(right,mid+1,e);
  31.  
  32.     tree[node]=tree[left]+tree[right];
  33.  
  34. }
  35.  
  36. void update(ll node,ll b,ll e,ll i,ll newv)
  37. {
  38.     if(i>e || i<b) return;
  39.  
  40.     if(b==e)
  41.     {
  42.         tree[node]=newv;
  43.         return;
  44.     }
  45.  
  46.     ll left = node*2;
  47.     ll right = node*2 + 1ll;
  48.  
  49.     ll mid=(b+e)/2;
  50.  
  51.     update(left,b,mid,i,newv);
  52.  
  53.     update(right,mid+1,e,i,newv);
  54.  
  55.     tree[node]=tree[left]+tree[right];
  56.  
  57. }
  58.  
  59. ll queries(ll node,ll b,ll e,ll i,ll j)
  60. {
  61.     if(i>e || j<b) return 0;
  62.  
  63.     if(b>=i && e<=j) return tree[node];
  64.  
  65.  
  66.     ll left = node*2;
  67.     ll right = node*2 + 1ll;
  68.  
  69.     ll mid=(b+e)/2;
  70.  
  71.     ll x=queries(left,b,mid,i,j);
  72.  
  73.     ll y=queries(right,mid+1,e,i,j);
  74.  
  75.     return x+y;
  76.  
  77. }
  78.  
  79.  
  80.  
  81. int main()
  82. {
  83.     ios_base::sync_with_stdio(0);
  84.     cin.tie(0);
  85.     cout.tie(0);
  86.  
  87.  
  88.     test
  89.     {
  90.         ll n,m,i,j,k,l,q;
  91.         char ch;
  92.  
  93.         cin>>n>>q;
  94.  
  95.         k=n;
  96.  
  97.         for(i=1; i<=n; i++)
  98.         {
  99.             cin>>a[i];
  100.         }
  101.  
  102.         treeconstruct(1,1,k*2);
  103.  
  104.         cout<<"Case "<<cs<<":"<<endl;
  105.  
  106.         while(q--)
  107.         {
  108.             cin>>ch>>m;
  109.  
  110.             if(ch=='a')
  111.             {
  112.                 n++;
  113.                 a[n]=m;
  114.                 update(1,1,k*2,n,1);
  115.             }
  116.             else
  117.             {
  118.                 ll lo=1,hi=n,mid,ans=0;
  119.  
  120.                 while(lo<=hi)
  121.                 {
  122.                     mid=(lo+hi)/2;
  123.  
  124.                     if(queries(1,1,k*2,1,mid)>=m)
  125.                     {
  126.                         ans=mid;
  127.                         hi=mid-1;
  128.                     }
  129.                     else lo=mid+1;
  130.                 }
  131.  
  132.                 if(ans)
  133.                 {
  134.                     cout<<a[ans]<<"\n";
  135.                     update(1,1,k*2,ans,0ll);
  136.                 }
  137.                 else cout<<"none"<<"\n";
  138.             }
  139.         }
  140.     }
  141.  
  142.  
  143.     get_lost_idiot;
  144. }
  145.  
RAW Paste Data