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.
