I tried using the segment tree and storing vectors in its node and merging them for sorting but still getting an error saying Submission Not Judged!
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
vector merge(vector a , vector b){
vector c ;
ll i = 0 ;
ll j = 0 ;
while(i < a.size() && j < b.size()){
if(a[i] < b[j]){
c.push_back(a[i++]);
}else{
c.push_back(b[j++]);
}
}
while(i < a.size()){
c.push_back(a[i++]);
}
while(j < b.size()){
c.push_back(b[j++]);
}
return c ;
}
void buildST(ll arr[] , ll s , ll e , vector< vector > &tree , ll index){
if(s==e){
vector temp ;
temp.push_back(arr[s]) ;
tree[index] = temp ;
return;
}
ll mid = (s+e)/2 ;
buildST(arr ,s , mid , tree , 2index) ;
buildST(arr ,mid+1 , e , tree , 2index+ 1) ;
tree[index] = merge(tree[2 * index] , tree[2*index + 1] ) ;
return;
}
ll query(vector<vector > &tree,ll s,ll e,ll l,ll r,ll key,ll index){
if(s>=l && e<=r){
vector::iterator lower;
vector vec=tree[index];
lower=lower_bound(vec.begin(),vec.end(),key);
return (vec.end()-lower);
}
if(l>e || r<s){
return 0;
}
ll mid=(s+e)/2;
ll left=query(tree,s,mid,l,r,key,2*index);
ll right=query(tree,mid+1,e,l,r,key,2*index+1);
return left+right;
}
int main(){
ll n;
cin>>n;
ll arr[n];
for(ll i=0;i<n;++i){
cin >> arr[i] ;
}
ll q ;
cin >> q ;
vector<vector> tree (4*n+1,vector (n+1));
buildST(arr , 0 , n-1 , tree , 1) ;
while(q–){
ll l,r,key;
cin >>l>>r>>key;
cout<<query(tree,0,n-1,l-1,r-1,key,1)<<endl;
}
return 0;
}