fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp> 
  3. #include <ext/pb_ds/tree_policy.hpp> 
  4. #define ll long long int
  5. #define lc                      ((n)<<1)
  6. #define rc                      ((n)<<1|1)
  7. #define pb push_back
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10.  
  11. typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, 
  12.              tree_order_statistics_node_update> pds; 
  13.  
  14.  
  15. ll n;
  16. const ll N=463005;
  17. vector <ll> arr(N);
  18. pds mst[N];
  19.  
  20. void init(ll pp)
  21. {
  22.     for(ll i=0;i<4*pp;i++)
  23.     {
  24.         mst[i].clear();
  25.     }
  26. }
  27.  
  28. void build(ll n,ll b,ll e)
  29. {
  30.     if(b==e)
  31.     {
  32.         mst[n].insert({arr[b],b});
  33.         return;
  34.     }
  35.     for(ll i=b;i<=e;i++)
  36.         mst[n].insert({arr[i],i});
  37.  
  38.     ll mid=(b+e)/2;
  39.     build(lc,b,mid);
  40.     build(rc,mid+1,e);
  41. }
  42.  
  43. ll query(ll n,ll b,ll e,ll i,ll j,ll v,ll idx)
  44. {
  45.     if(b>j or e<i)  return 0;
  46.     if(b>=i and e<=j)
  47.     {
  48.         ll k=mst[n].order_of_key({v,idx});
  49.         return k;
  50.     }
  51.     ll mid=(b+e)/2;
  52.     return query(lc,b,mid,i,j,v,idx) + query(rc,mid+1,e,i,j,v,idx);
  53. }
  54.  
  55. void update(ll n,ll b,ll e,ll i,ll v,ll nw)
  56. {
  57.     if(i<b or e<i)  return;
  58.     if(b==i and e==i)
  59.     {
  60.         mst[n].erase(mst[n].find({v,i}));
  61.         mst[n].insert({nw,i});
  62.         return;
  63.     }
  64.     ll mid=(b+e)/2;
  65.     update(lc,b,mid,i,v,nw);
  66.     update(rc,mid+1,e,i,v,nw);
  67.     mst[n].erase(mst[n].find({v,i}));
  68.     mst[n].insert({nw,i});
  69. }
  70.  
  71. int main()
  72. {
  73.  
  74.     ll test,i,j,queries;
  75.     scanf("%lld",&test); // number of test cases
  76.     while(test--)
  77.     {
  78.  
  79.         scanf("%lld",&n);  //number of elements in the array
  80.         init(n);        // initializing the policy based tree
  81.  
  82.         for(i=1;i<=n;i++)
  83.         {
  84.             scanf("%lld",&arr[i]);  //scanning the array
  85.         }
  86.  
  87.         build(1,1,n);
  88.  
  89.         cin>>queries;       //number of queries
  90.         while(queries--)
  91.         {
  92.             ll choice;
  93.             scanf("%lld",&choice);      //if choice is 0 -> it represents query, choice 1 -> represents update
  94.             if(choice==0)
  95.             {
  96.                 ll l,r,x;
  97.                 scanf("%lld %lld %lld",&l,&r,&x);       //  the x-th number in sorted a[l ... r] segment
  98.  
  99.                 ll low = mst[1].find_by_order(0)->first, high = mst[1].find_by_order(n-1)->first , mid, ans ;
  100.  
  101.                 // binary search to find the x-th number
  102.  
  103.                 while(low <= high) 
  104.                 {
  105.                     mid = low + high >> 1;
  106.                     ll k = query(1,1,n,l,r,mid,1005);       // i have considered the highest element in the array to be 1000, change according to your program
  107.                     if(k >=x ) 
  108.                     {
  109.                         ans = mid;
  110.                         high = mid-1;
  111.                     }
  112.                     else low = mid+1;
  113.                 }
  114.  
  115.                 printf("%lld\n",ans);
  116.  
  117.             }
  118.             else
  119.             {               
  120.                 // Update the profit of the idx-th shop to x
  121.  
  122.                 ll idx,x;
  123.                 scanf("%lld %lld",&idx,&x);
  124.                 update(1,1,n,idx,arr[idx],x);
  125.                 arr[idx]=x;
  126.             }
  127.  
  128.         }
  129.  
  130.     }
  131.     return 0;
  132.  
  133. }
Success #stdin #stdout 0.03s 50036KB
comments (?)
stdin
copy 
1
4
5 3 2 1
3
0 1 1 1
1 1 1
0 1 4 3
stdout
copy 
5
2
https://ideone.com/kQrfVe
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!