I am getting Run Time Error in MULTQ3 <http://www.spoj.pl/problems/MULTQ3/>. I have implemented the segment tree and i can't understand why i can get the run time error in spoj judge. I tried to generate random input values and they ran fine on my system.
If i try to increase the MAX value then TLE starts to appear. Since value of N<=100000 so MAX 500000 is more than enough to accommodate all nodes in segment tree. #include<cstdio> #include<algorithm> #include<memory.h> using namespace std; #define MAX 500000 int M1[2*MAX+1]; int M2[2*MAX+1]; int flag[2*MAX+1]; void Refresh(int node,int begin,int end) { int temp = M2[node]; M2[node] = M1[node]; M1[node] = (end - begin) + 1 - M1[node] - temp; flag[node]--; flag[node*2] = (flag[2*node]+1)%3; flag[2*node+1] = (flag[2*node+1]+1)%3; } int query(int node, int b, int e, int i, int j) { if(b>j || e<b || j<i) { return 0; } while(flag[node]>0) { Refresh(node, b, e); } if(b==i && e==j) { return (e-b+1 - M1[node]-M2[node]); } int mid = (b+e)>>1; return query(2*node, b, mid, max(i, b), min(j,e)) + query(2*node+1, mid+1, e, max(mid+1,i) ,min(e,j) ); } void update(int node, int b, int e,int i, int j) { if(i > e || j<b) return; while(flag[node]>0) { Refresh(node, b, e); } if( b>=i && e<=j) { if(flag[node]==0) { Refresh(node, b, e); } if(flag[node]==1) { Refresh(node, b, e); Refresh(node, b, e); } flag[node] = 0; return; } else if(b>=e) { return; } else { int mid = (b+e)>>1; if(i<=mid) { update(2*node, b, mid, i, j); } if(j>mid) { update(2*node+1, mid+1, e, i, j); } while(flag[2*node]>0) { Refresh(2*node, b ,mid); } while(flag[2*node+1]>0) { Refresh(2*node+1, mid+1, e); } M1[node] = M1[node*2] + M1[2*node+1]; M2[node] = M2[2*node] + M2[2*node+1]; } } int main() { int N,m,u,v,ch; memset(M1,0,sizeof(M1)); memset(M2,0,sizeof(M2)); memset(flag, 0, sizeof(flag)); scanf("%d %d",&N,&m); for(int i=0;i<m;i++) { scanf("%d %d %d",&ch,&u,&v); if(ch==0) update(1, 1, N, u+1, v+1); else printf("%d\n",query(1, 1, N, u+1, v+1)); } } Aamir Khan | 3rd Year | Computer Science & Engineering | IIT Roorkee -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.