fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. #define fast std::ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
  7. #define ll long long
  8. #define test cout<<"archit\n"
  9. #define debug(x) cout<<x<<" "
  10. #define debug1(x) cout<<x<<"\n"
  11. #define debug2(x,y) cout<<x<<" "<<y<<"\n"
  12. #define pb push_back
  13. #define pi pair<int,int>
  14. #define fi first
  15. #define si second
  16. #define mod (ll)1000000007
  17. #define mxn 1000005
  18. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  19. using namespace std;
  20. using namespace __gnu_pbds;
  21. typedef struct trienode
  22. {
  23.     int val;
  24.     vector<int>v;
  25.     struct trienode* child[2];
  26. }trienode;
  27. trienode* newNode()
  28. {
  29.     trienode* t = new trienode;
  30.     t->v.clear();
  31.     t->val=0;
  32.     t->child[0]=t->child[1]=NULL;
  33.     return t;
  34. }
  35. void insert(trienode* root, int value, int index)
  36. {
  37.     trienode* curr = root;
  38.     for(int i=31;i>=0;i--){
  39.         bool bit = value&(1<<i);
  40.         if(curr->child[bit] == NULL){
  41.             curr->child[bit] = newNode();
  42.         }
  43.         curr->child[bit]->v.pb(index);
  44.         curr = curr->child[bit];
  45.     }
  46.     curr->val = value;
  47.     return;
  48. }
  49. bool lieBetweenRange(vector<int>v, int left, int right)
  50. {
  51.     if(v.size() == 0){
  52.         return false;
  53.     }
  54.     if(v[0]>right || v[v.size()-1]<left){
  55.         return false;
  56.     }
  57.     int l=0,r=v.size()-1;
  58.     while(l<=r){
  59.         int mid = l+(r-l)/2;
  60.         if(v[mid]>=left && v[mid]<=right){
  61.             return true;
  62.         }
  63.         if(v[mid]<left){
  64.             l=mid+1;
  65.         }
  66.         else if(v[mid]>right){
  67.             r=mid-1;
  68.         }
  69.     }
  70.     return false;
  71. }
  72. int getQuery(trienode* root, int l, int r, int value)
  73. {
  74.     trienode* curr = root;
  75.     for(int i=31;i>=0;i--){
  76.         bool bit = value&(1<<i);
  77.         if(curr->child[1-bit]!=NULL){
  78.             vector<int>temp = curr->child[1-bit]->v;
  79.             if(lieBetweenRange(temp, l, r) == true){
  80.                 //test;
  81.                 curr = curr->child[1-bit];
  82.             }
  83.         }
  84.         else if(curr->child[bit]!=NULL){
  85.             vector<int>temp = curr->child[bit]->v;
  86.             if(lieBetweenRange(temp, l, r) == true){
  87.                 curr = curr->child[bit];
  88.             }
  89.         }
  90.     }
  91.     return curr->val;
  92. }
  93. int main()
  94. {
  95.     fast;
  96.     int q; cin>>q;
  97.     int type,l,r,val;
  98.     trienode* root = newNode();
  99.     int index=1;
  100.     for(int i=1;i<=q;i++){
  101.         cin>>type;
  102.         if(type == 0){
  103.             cin>>val;
  104.             insert(root, val, index);
  105.             index+=1;
  106.         }
  107.         else{
  108.             cin>>l>>r>>val;
  109.             debug1(getQuery(root, l, r, val));
  110.         }
  111.     }
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RPeNyt
language:
C++14 (gcc 8.3)
created:
6 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!