Now its done. Still gives TLE in 3-4 cases.
Code: https://www.codechef.com/viewsolution/13789884
My code is giving NZEC in certain cases. Can anyone please help why is this happening?
class CHEFSUBA
{
public static void main(String[] args) throws IOException
{
boolean readFromFile = false;
boolean outputToFile = false;
CustomInputOutputClass cio = new CustomInputOutputClass(readFromFile, outputToFile);
int[] temp = cio.readIntegerArrayFromSingleLine();
int n = temp[0];
int k = temp[1];
int p = temp[2];
int[] origArr = cio.readIntegerArrayFromSingleLine();
String queryString = cio.readString();
ArrayList<Integer> answerList = new ArrayList<Integer>();
int length = origArr.length;
int[] arr = new int[2 * length];
int arrLength = 2 * length;
int[] maxArray = new int[arrLength - k + 1];
for(int i = 0; i < 2 * length; i++)
{
arr[i] = origArr[i % length];
}
for(int i = 0; i < length; i++)
{
int t = arr[i];
arr[i] = arr[2 * length - 1 - i];
arr[2 * length - 1 - i] = t;
}
int count = 0;
for(int i = 0; i < k; i++)
{
count = count + arr[i];
}
maxArray[0] = count;
for(int i = 1; i < arrLength - k + 1; i++)
{
maxArray[i] = maxArray[i - 1] - arr[i - 1] + arr[i + k - 1];
}
/*
for(int x: maxArray)
System.out.print(x + "\t");
System.out.println();
*/
Deque<Integer> deque = new LinkedList<Integer>();
for(int i = 0; i < length - k + 1; i++)
{
if(deque.isEmpty())
deque.addFirst(i);
else
{
if(maxArray[i] < maxArray[deque.getLast()])
deque.addLast(i);
else
{
while(!deque.isEmpty() && maxArray[deque.getLast()] <= maxArray[i])
deque.removeLast();
deque.addLast(i);
}
}
}
//for(int x: deque)
// System.out.print(x + "\t");
answerList.add(maxArray[deque.getFirst()]);
count = 0;
for(int i = length - k + 1; i < maxArray.length; i++)
{
if(deque.getFirst() == count)
deque.removeFirst();
if(deque.isEmpty())
deque.addFirst(i);
else
{
if(maxArray[i] < maxArray[deque.getLast()])
deque.addLast(i);
else
{
while(!deque.isEmpty() && maxArray[deque.getLast()] <= maxArray[i])
deque.removeLast();
deque.addLast(i);
}
}
answerList.add(maxArray[deque.getFirst()]);
count++;
}
//for(int x: answerList)
// System.out.print(x + "\t");
count = 0;
for(int i = 0; i < queryString.length(); i++)
{
char query = queryString.charAt(i);
if(query == '?')
System.out.println(answerList.get(count));
else if(query == '!')
count++;
}
cio.cleanup();
}
}
My solution is showing TLE for few cases. Please help.
can any1 give me d solution which is solved using sparse tables ??
@rj25 plz explain purpose of these lines :
for(int k=n-f;k>=0;k–)frames.push_back(fr[k]);
for(int i=n-1;i>0;i–)frames.push_back(fr[i]);
in your code.
The given pseudo code generates a different sum array…can anyone please explain how the given sum array is generated…@likecs @admin
i think sum[0]=b[0] …instead of sum[0]=0
How to compute the answer using this sum array…
https://www.codechef.com/viewsolution/14939652
My simple and easy to understand solution… And for all struggling with the "Sum array " part…sum[i] denotes the number of 1 in the range inp[i-k] to inp[i]…