I HAVE TRIED THIS PROBLEM IN THREE WAYS USING ARRAY WITH QUICK SORTING, LINKED LIST AND WITH HEAP. BUT IN ALL OF THEM, ONLY ONE TEST CASE IS PASSING EITHER FIRST OR SECOND. THIS CODE IS USING HEAP AND IT HAS PASSED ONLY SECOND CASE WHILE FIRST SHOWS ‘TLE’. PLEASE HELP ME WITH THIS CODE.
import java.util.;
public class HostelVisit
{
ArrayList data=new ArrayList<>();
public void add(int item)
{
data.add(item);
upheapify(data.size()-1);
}
private void upheapify(int ci)
{
int pi=(ci-1)/2;
if(data.get(pi)>data.get(ci)) //if we use >= then there is need of base case
{
swap(pi,ci);
upheapify(pi);
}
}
private void swap(int i,int j)
{
int ith=data.get(i); //
int jth=data.get(j);
data.set(i,jth);
data.set(j,ith);
}
public void display()
{
System.out.println(data);
}
public int size()
{
return this.data.size();
}
public boolean isEmpty()
{
return this.size()==0;
}
public int get()
{
return this.data.get(0);
}
public int remove()
{
swap(0,this.data.size()-1); ///
int rv=this.data.remove(this.data.size()-1);
downheapify(0);
return rv;
}
private void downheapify(int pi)
{
int lci=2pi+1;
int rci=2*pi+2;
int mini=pi;
if(lci<data.size()&&data.get(lci)<data.get(mini))
mini=lci;
if(rci<data.size()&&data.get(rci)<data.get(mini))
mini=rci;
if(mini!=pi)
{
swap(mini,pi);
downheapify(mini);
}
}
public int getK(int k)
{
int i=1;
ArrayList<Integer> list=new ArrayList<>();
while(i<k)
{
list.add(remove());
i++;
}
int ans=this.get();
while(!list.isEmpty())
add(list.remove(0));
return ans;
}
public static void main(String[] args)
{
HostelVisit heap=new HostelVisit();
Scanner sc=new Scanner(System.in);
int i,Q=sc.nextInt();
int K=sc.nextInt();
for(i=0;i<Q;i++)
{
int n=sc.nextInt();
if(n==1)
{
int x=sc.nextInt();
int y=sc.nextInt();
int distance=x*x + y*y;
heap.add(distance);
}
else if(n==2)
{
System.out.println(heap.getK(K));
}
}
}
}