My c++ solution got accepted. But same process for java causing memory limit exceeded error. can any one explain ??? it's a segment tree problem . I am just switching my language from cpp to java. but i am facing problem while submitting in different on line judges. As in this case same code in c++ got accepted.
Any tips to solve problem in java will definitely help me. I am in great danger.
my code
import java.util.*;
class segmnetTree {
int [] array, segarray; segmnet() { array=new int[100001]; segarray=new int[400001]; } int left(int n) { return 2*n; } int right( int n) { return 2*n+1; } void brmq(int p, int l, int r) { if(l==r) { segarray[p]=array[l]; return; } brmq(left(p),l,(l+r)/2); brmq(right(p),(l+r)/2+1,r); segarray[p]=Math.min(segarray[left(p)],segarray[right(p)]); } int rmq( int p,int l, int r, int i, int j) { if(i>r || j<l) return -1; // MAXXXX or set it in a way to understand else if(l>=i && r<=j) return segarray[p]; int a1=rmq( left(p), l,(l+r)/2, i,j); int a2=rmq( right(p), (l+r)/2+1 , r , i,j); if(a1==-1) return a2; if(a2==-1) return a1; else return Math.min(a1,a2); }
}
public class SegmentTree {
public static void main(String[] args) { segmnet s1=new segmnet(); Scanner sin=new Scanner(System.in); int cas=sin.nextInt(); for( int cno=1; cno<=cas;cno++) { int n,q; n=sin.nextInt(); q=sin.nextInt(); for( int m=1;m<=n;m++) { s1.array[m]=sin.nextInt(); } s1.brmq(1,1,n); System.out.println("Case "+cno+":"); for( int m=0;m<q;m++) { int i,j; i=sin.nextInt(); j=sin.nextInt(); System.out.println(s1.rmq(1,1,n,i,j)); } } }
}
Scanner tends to be quite slow reading the input (enough for TLE). Try a faster input reader, e.g. check Petr's — http://codeforces.net/contest/700/submission/19337666
I didn't get TLE. my memory limit was exceeded. but thanks for your help. :)
I'm sorry, I misread. I'm not seeing a reason for MLE, even stack size overlow seems unlikely.
It's an issue with lightoj. Write this line " System.exit(0); " in the last line of main method. MLE issue will be fixed.
I faced the same problem with segment trees in C# but I changed all long numbers to int .
I don't see the reason to MLE with you .
try another DS .I don't think there will be a solution for this issue here .