implement segment tree with lazy propagation :) On Tue, Sep 27, 2011 at 1:19 PM, Aamir Khan <[email protected]> wrote:
> I am trying to solve http://www.spoj.pl/problems/LITE/ using segment tree. > Here's the code but i am getting TLE. Can somebody help me to optimize the > code ? > > #include<cstdio> > #include<algorithm> > > struct node{ > int l; > int r; > bool el ; > node *left; > node *right; > }; > > struct node *build(int l, int r) { > struct node *root = new node; > root->l = l; > root->r = r; > root->el = 0; > if(l==r) { > root->left=NULL; > root->right=NULL; > return root; > } > root->left = build(l,(l+r)/2); > root->right= build((l+r)/2+1,r); > return root; > } > > int query(struct node *root, int l, int r) { > if(root==NULL || r<l) > return 0; > > if((root->el) && (root->l)<=l && (root->r)>=r) { > return (r - l + 1); > } > > int mid = (root->l + root->r)/2; > return query(root->left, l, std::min(mid,r)) + query(root->right, > std::max(mid+1,l), r); > > } > > void update(struct node *root, int l,int r) { > if(root->l==l && root->r==r && (root->left==NULL || root->el)) { > root->el = 1 - root->el; > return; > } > > if(root->el) { > root->left->el = 1; > root->right->el = 1; > root->el = 0; > } > > int mid = (root->l + root->r)/2; > if(l <= mid) > update(root->left, l, std::min(mid,r)); > if(r > mid) > update(root->right, std::max(mid+1,l), r); > } > > int main() { > int N, M; > scanf("%d %d",&N,&M); > struct node *root = build(1,N); > int L,R; > int c; > while(M--) { > scanf("%d %d %d\n",&c,&L,&R); > if(c==0) > update(root, L, R); > else > printf("%d\n",query(root,L,R)); > } > return 0; > } > > > > > > 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. > -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,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.
