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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
