Advertisement
anujstarlord

Untitled

Aug 15th, 2022
466
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.29 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. static bool cmp(vector<int>& a,vector<int>& b)
  4. {
  5.     if(a[0]<b[0])
  6.         return true;
  7.     else
  8.         return false;
  9. }
  10.  void asb(long long node,int i,int j,vector<vector<int>>&  nums,vector<int>& a)
  11.     {
  12.      
  13.         if(i==j)
  14.         {
  15.             a[node]=nums[i][1];
  16.             return ;
  17.         }
  18.         else
  19.         {
  20.             int mid=i+(j-i)/2;
  21.             asb(2*node+1,i,mid,nums,a);
  22.             asb(2*node+2,mid+1,j,nums,a);
  23.             a[node]=max(a[2*node+1],a[2*node+2]);
  24.         }
  25.     }
  26.  int maxval(int start,int end,int l,int r,long long node,vector<int>& a)
  27.     {
  28.         if(start==l && end==r)
  29.         {
  30.             return a[node];
  31.         }
  32.         else
  33.         {
  34.            
  35.             int mid=start+(end-start)/2;
  36.             if(l<=mid && r>mid)
  37.             {
  38.                 int f=maxval(start,mid,l,mid,2*node+1,a);
  39.                 int b=maxval(mid+1,end,mid+1,r,2*node+2,a);
  40.                 return max(f,b);
  41.             }
  42.             if(r<=mid)
  43.                 return maxval(start,mid,l,r,2*node+1,a);
  44.             else
  45.                 return maxval(mid+1,end,l,r,2*node+2,a);
  46.            
  47.         }
  48.     }
  49. int maxRange(vector<int>& a,int left, int right,int size) {
  50.        
  51.      
  52.        int d=maxval(0,size,left,right,0,a);
  53.        
  54.        
  55.         return d;
  56.     }
  57.  
  58.  
  59.  
  60.  
  61.  
  62. vector<int> solve(int N ,vector<vector<int>>& arr,int Q,vector<vector<int>> & query)
  63. {
  64.     vector<int> a(4*arr.size());
  65.     sort(arr.begin(),arr.end(),cmp);
  66.     asb(0,0,arr.size()-1,arr,a);
  67.     vector<int> ans;
  68.    
  69.    for(auto i: query)
  70.    { sort(i.begin(),i.end());
  71.        int start=0,end=arr.size()-1;
  72.        while(start<=end)
  73.        {
  74.            int mid=start+(end-start)/2;
  75.            if(arr[mid][0]>=i[0])
  76.                end=mid-1;
  77.            else
  78.                start=mid+1;
  79.                
  80.        }
  81.     int start_idx=start;
  82.     start=0,end=arr.size()-1;
  83.        while(start<=end)
  84.        {
  85.            int mid=start+(end-start)/2;
  86.            if(arr[mid][0]>i[1])
  87.                end=mid-1;
  88.            else
  89.                start=mid+1;
  90.        }
  91.       if(start_idx>end)
  92.           ans.push_back(-1);
  93.     else
  94.         ans.push_back(maxRange(a,start_idx,end,arr.size()-1));
  95.    
  96.    }
  97.    
  98.     return ans;
  99. }
  100.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement