[BUG] - Runtime too strict Giving TLE #32393
Description
LeetCode Username
Harshil_gandhi
Problem Number, Title, and Link
- Minimum Threshold for Inversion Pairs Count https://leetcode.com/problems/minimum-threshold-for-inversion-pairs-count/description/
Bug Category
Problem constraints
Bug Description
My solution is O(n*log(n)*log(1e9)) , where n=10000 which should do max 4.2 *10^6 operations
Language Used for Code
Cpp
Code used for Submit/Run operation
class Solution {
public:
class Segment{
public:
int maxi[40004],mini[40004];
Segment(int n){
memset(maxi,0,sizeof(maxi));
memset(mini,0,sizeof(mini));
}
void build(int v,vector<int>&nums,int tl,int tr){
if(tl==tr){
maxi[v]=mini[v]=nums[tl];
return ;
}
int m=tl+(tr-tl)/2;
build(2*v,nums,tl,m);
build(2*v+1,nums,m+1,tr);
maxi[v]=max(maxi[2*v],maxi[2*v+1]);
mini[v]=min(mini[2*v],mini[2*v+1]);
}
int queryMaxi(int v,int tl,int tr,int l,int r,int val){
if(tr<l || r<tl) return 0;
if(l<=tl && r>=tr && mini[v]>=val) return tr-tl+1;
if(l<=tl && r>=tr && maxi[v]<val) return 0;
int m=tl+(tr-tl)/2;
int left=queryMaxi(2*v,tl,m,l,r,val);
int right=queryMaxi(2*v+1,m+1,tr,l,r,val);
return left+right;
}
int queryMini(int v,int tl,int tr,int l,int r,int val){
if(tr<l || r<tl) return 0;
if(l<=tl && r>=tr && maxi[v]<val) return tr-tl+1;
if(l<=tl && r>=tr && mini[v]>=val) return 0;
int m=tl+(tr-tl)/2;
int left=queryMini(2*v,tl,m,l,r,val);
int right=queryMini(2*v+1,m+1,tr,l,r,val);
return left+right;
}
};
int minThreshold(vector<int>& nums, int k) {
int n=nums.size();
if(((n*(n-1))/2)<k) return -1;
Segment sg(n);
sg.build(1,nums,0,n-1);
vector<pair<int,int>>temp;
for(int i=0;i<n;i++) temp.push_back({nums[i],i});
sort(temp.begin(),temp.end());
int maxi=temp.back().first-temp[0].first;
int s=0,e=maxi;
while(s<=e){
int m=s+(e-s)/2,total=0;
cout<<m<<" "<<endl;
for(int i=n-1;i>=0;i--){
int ind=temp[i].second,val=temp[i].first;
total+=(n-ind-1)-sg.queryMini(1,0,n-1,ind+1,n-1,val-m)-sg.queryMaxi(1,0,n-1,ind+1,n-1,val);
if(total>=k) break;
}
if(total>=k) e=m-1;
else s=m+1;
}
if(s>maxi) return -1;
return s;
}
};Expected behavior
Should be coming accepted
Screenshots
Additional context
No response