fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int tree[5000000];
  5.  
  6. void update(int node,int st,int end,int ind,int val)
  7. {
  8.     if(st==end)
  9.     {
  10.         tree[node]=val;
  11.         return;
  12.     }
  13.  
  14.     int mid=(st+end)/2;
  15.  
  16.     if(ind<=mid)
  17.         update((2*node),st,mid,ind,val);
  18.     else
  19.         update((2*node)+1,mid+1,end,ind,val);
  20.  
  21.     tree[node]=tree[(node*2)]+tree[(node*2)+1];
  22.     return;
  23. }
  24.  
  25. int query(int node,int st,int end,int k)
  26. {
  27.     if(st==end)
  28.     {
  29.         return st;
  30.     }
  31.  
  32.     int  mid=(st+end)/2;
  33.  
  34.     if(tree[2*node]>=k)
  35.         return query(2*node,st,mid,k);
  36.     else
  37.         return query((node*2)+1,mid+1,end,k-tree[2*node]);
  38. }
  39. int main()
  40. {
  41.     int n,t,a,b;
  42.     cin>>n;
  43.  
  44.     for(int i=0;i<5000000;i++)
  45.         tree[i]=0;
  46.  
  47.     for(int i=0;i<n;i++)
  48.     {
  49.         update(1,1,n,i+1,1);
  50.     }
  51.  
  52.     cin>>t;
  53.     while(t--)
  54.     {
  55.         cin>>a>>b;
  56.         if(a==0)
  57.         {
  58.             update(1,1,n,b,0);
  59.         }
  60.         else
  61.         {
  62.             if(b>tree[1])
  63.             cout<<"-1\n";
  64.             else
  65.             cout<<query(1,1,n,b)<<"\n";
  66.         }
  67.     }
  68.     return 0;
  69. }
Success #stdin #stdout 0.01s 23124KB
comments (?)
stdin
copy 
6
3
1 5
0 2
1 5
stdout
copy 
5
6
https://ideone.com/TOCjeo
language:
C++ (gcc 8.3)
created:
4 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!