Hi All , I am practising some SPOJ problems in Java which I have already solved in Cpp but keep getting TLE can some one suggest me how to get AC with Java My same algorithm got AC in .18s (Cpp)
below is my code
.`/**
*
*/
/**
* @author Lakshman
*
*/
//package com.spoj.my.solution;
import java.io.BufferedOutputStream;
import java.io.DataInputStream;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Stack;
class Pair<K, V> {
private final K element0;
private final V element1;
public static <K, V> Pair<K, V> createPair(K element0, V element1) {
return new Pair<K, V>(element0, element1);
}
public Pair(K element0, V element1) {
this.element0 = element0;
this.element1 = element1;
}
public K getElement0() {
return element0;
}
public V getElement1() {
return element1;
}
}
public class Main {
static class Parser {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Parser(InputStream in) {
din = new DataInputStream(in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public int nextInt() throws Exception {
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = c == '-';
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
c = read();
} while (c > ' ');
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws Exception {
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws Exception {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
}
public static int[][] Idx = new int[100005][2];
public static int[][] Idx1 = new int[100005][2];
public static void lookup(int N) {
int c = 0;
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
for (int i = 0; i < N; i++) {
if (Idx[i][0] != -1) {
out.println((Idx[i][0] + 1) + " " + (Idx1[i][0] + 1));
} else {
out.println("-1,-1");
}
}
out.flush();
}
public static void Solver(ArrayList<Pair<Integer, Integer>> Q, int N) {
Pair<Integer, Integer> Tmp = new Pair<>(0, 0);
Iterator<Pair<Integer, Integer>> T = Q.iterator();
if (T.hasNext()) {
Tmp = T.next();
}
Stack<Pair<Integer, Integer>> S = new Stack<>();
S.add(Tmp);
while (T.hasNext()) {
Pair<Integer, Integer> Tmp1 = T.next();
while (!S.empty() && S.peek().getElement1() < Tmp1.getElement1()) {
for (int i = 0; i < 2; i++) {
if (Idx[S.peek().getElement0()][i] != Integer.MAX_VALUE)
continue;
Idx[S.peek().getElement0()][i] = Tmp1.getElement0();
}
S.pop();
}
S.push(Tmp1);
}
while (!S.empty()) {
for (int i = 0; i < 2; i++) {
if (Idx[S.peek().getElement0()][i] != Integer.MAX_VALUE)
continue;
Idx[S.peek().getElement0()][i] = -1;
}
S.pop();
}
}
public static void Solver1(ArrayList<Pair<Integer, Integer>> Q, int N) {
Pair<Integer, Integer> Tmp = new Pair<>(0, 0);
Iterator<Pair<Integer, Integer>> T = Q.iterator();
if (T.hasNext()) {
Tmp = T.next();
}
Stack<Pair<Integer, Integer>> S = new Stack<>();
S.add(Tmp);
while (T.hasNext()) {
Pair<Integer, Integer> Tmp1 = T.next();
while (!S.empty() && S.peek().getElement1() < Tmp1.getElement1()) {
for (int i = 0; i < 2; i++) {
if (Idx1[S.peek().getElement0()][i] != Integer.MAX_VALUE)
continue;
Idx1[S.peek().getElement0()][i] = Tmp1.getElement0();
}
S.pop();
}
S.push(Tmp1);
}
while (!S.empty()) {
for (int i = 0; i < 2; i++) {
if (Idx1[S.peek().getElement0()][i] != Integer.MAX_VALUE)
continue;
Idx1[S.peek().getElement0()][i] = -1;
}
S.pop();
}
}
public static void main(String[] args) throws Exception {
int T;
Parser aa = new Parser(System.in);
T = aa.nextInt();
for (int cs = 1; cs <= T / 2; cs++) {
int N = aa.nextInt();
for (int i = 0; i < 100005; i++) {
for (int j = 0; j < 2; j++) {
Idx[i][j] = Integer.MAX_VALUE;
Idx1[i][j] = Integer.MAX_VALUE;
}
}
int inputs[] = new int[N + 1];
for (int i = 0; i < N; i++)
inputs[i] = aa.nextInt();
ArrayList<Pair<Integer, Integer>> inpr = new ArrayList<>();
ArrayList<Pair<Integer, Integer>> rinp = new ArrayList<>();
for (int i = 0; i < N; i++) {
inpr.add(new Pair<>(N - i - 1, inputs[N - i - 1]));
}
for (int i = 0; i < N; i++) {
inpr.add(new Pair<>(N - i - 1, inputs[N - i - 1]));
}
for (int i = 0; i < N; i++) {
rinp.add(new Pair<>(i, inputs[i]));
}
for (int i = 0; i < N; i++) {
rinp.add(new Pair<>(i, inputs[i]));
}
Main.Solver(inpr, N);
Main.Solver1(rinp, N);
lookup(N);
}
}
}
`