i couldn’t find the error according to me logic seems to be right .if some one is using premium pls tell me atleast where my code is failed
My code
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
for (int p=0;p<t;p++)
{
int n,q;
cin>>n;
cin>>q;
int arr[n];
for (int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n);
vector<int> query(n-2);
for(int i=0;i<n-2;i++)
{
query[i]=((n-i-1)*(n-i-2))/2;
if (i>=1)
query[i]+=query[i-1];
}
for (int i=0;i<q;i++)
{
int a;
cin>>a;
cout<<arr[lower_bound(query.begin(),query.end(),a)-query.begin()]<<endl;
}
}
return 0;
}
@ramteja1937
U r getting error bcoz of integer overflow . just take all as long long int .
i have corrected your code include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
for (int p=0;p<t;p++)
{
long long int n,q;
cin>>n;
cin>>q;
long long int arr[n];
for (int i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n);
vector query(n-2);
for(int i=0;i<n-2;i++)
{
query[i]=((n-i-1)*(n-i-2))/2;
if (i>=1)
query[i]+=query[i-1];
}
for (int i=0;i<q;i++)
{
long long int a;
cin>>a;
cout<<arr[lower_bound(query.begin(),query.end(),a)-query.begin()]<<endl;
}
}
return 0;
Hi, I actually also solved this just now but i didnt get the optimal solution i.e., i couldnt speed it up and it gave me “TLE”. If u dont mind can you look at my code and guide me how i can optimize my code. Thank you.
include <stdio.h>
int min_oftriplet(int index,int ar[], int size)
{
//first we sort the arrAY.
int n=size;
for(int i=1;i<=n;i++)
{
int temp;
for(int j=i+1;j<=n;j++)
{
if(ar[i]>=ar[j])
{
temp=ar[i];
ar[i]=ar[j];
ar[j]=temp;
}
}
}
if(index>n){
return ar[1]; //if query is greater than the size of array return the smallest number .
}else
{
for(int i=1;i<=index;i++)
{
if(i+2>=index)
{
return ar[i];
}
}
}
}
int main(void) {
int t;
scanf("%d",&t);
while(t--)
{
int n,q;
scanf("%d %d",&n,&q);
int ar[n],quer[q];
for(int i=1;i<=n;i++)
{
scanf("%d",&ar[i]);
}
for(int i=1;i<=q;i++)
{
scanf("%d",&quer[i]);
}
for(int i=1;i<=q;i++)
{
printf("%d\n",min_oftriplet(quer[i],ar,n));
}
}
return 0;
@d_d26 u r getting tle bcoz your code complexity is O(n^2) and u have to do it in O(nlogn)
so to do so we have used binary search along with prefix precomputation which will be the optimal solution for the problem
@d_d26 actually its like we precompute some values and store it in some data structure from the prefix or suffix of the array to use it in future.
like in this prb precomputation part is this
for(int i=0;i<n-2;i++)
{
query[i]=((n-i-1)*(n-i-2))/2;
if (i>=1)
query[i]+=query[i-1];
}
