TLE in "Lost Guy Radhu" (MAY19F1)

help
, ,
1

my solution is giving tle in last 2 test cases
please help me optimize this code

import java.util.;
import java.io.;
class Codechef
{
public static void main(String args[])throws java.lang.Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
// ring s=br.readLine().trim().split(“\s+ “);
int t=Integer.parseInt(br.readLine().trim());
while(t–>0)
{ String s1[]=br.readLine().trim().split(”\s+”);
int n=Integer.parseInt(s1[0]);
int q=Integer.parseInt(s1[1]);
String s2[]=br.readLine().trim().split(“\s+”);
long ai[]=new long[n];
long qi[]=new long[q];
for(int i=0;i<n;i++)
ai[i]=Integer.parseInt(s2[i]);
String s3[]=br.readLine().trim().split(“\s+”);
for(int i=0;i<q;i++)
qi[i]=Integer.parseInt(s3[i]);
for(int i=0;i<q;i++)
{ long k=qi[i];
long max=0;

     for(int j=0;j<k;j++)
       {
        if(ai[j]>max)
         max=ai[j];
       }
       System.out.println(max);
   }
  }

}
}

2

You must process queries in constant time(no loop inside query loop).
Brute force wouldn’t be fast enough.

1 Like
3

but then without loop how to track the index?

4

Pre-calculate answer outside query loop.
Make an array max[n]. max[i] denotes maximum till i’th element .
Just output the required value from max inside query loop.

2 Likes