+1 to the editorialist, explanation is great, and mentioning the similar problems for practice, I really appreciate his efforts and Thanks!!
the time limit has been set dumbly , I implemented everything as in editorial but then also got tle , CodeChef: Practical coding for everyone
Hello all,
Is there some way of accessing the test cases for this problem statement? The contest judge declared that my solution was segfaulting. I generated test cases in the order as suggested in the problem statement which ran successfully in my machine, so I would like to check with the actual test cases where the segfaulting is occurring.
Thanks
Sudharshan
What it is not mentioned is how you really do the propagation,a key element in this problem. This was my biggest problem. Here the priority of operations is important. You cannot do the propagation how you want…
So if you propagate from a node to right node,you know that the updates from node where made later( because of propagation itself).
Let’s say sum in right node is X(after we make all updates with its vals , add and mul).Now we come with information from node,knowing it was made later,it comes like that:(X+a1+a2+a3)a4a5+a6 … So mul and add from right node become mul*=mulnode and add=add*mulnode+addnode
That observation was important to me and I spent some time thinking …
If any of you found a easier way,please let me know!
Can anyone properly explain how to propagate the add and mul values to the left and right node? I think that point is a bit unclear in the editorial.
Thanks a lot for the similar problems list
What is the problem with this solution?
using namespace std;
int main() {
long n, q, m = 1000000007L;
cin>>n>>q;
long a[n];
for(long i=0;i<n;i++) {
cin>>a[i];
}
long t, x,y, v;
for(long i=0;i<q;i++) {
cin>>t>>x>>y;
x--;
y--;
if(t==1) {
cin>>v;
for(long j=x;j<=y;j++) {
a[j]+=v;
a[j]%=m;
}
}
else if(t==2) {
cin>>v;
for(long j=x;j<=y;j++) {
a[j]*=v;
a[j]%=m;
}
}
else if(t==3) {
cin>>v;
for(long j=x;j<=y;j++) {
a[j]=v;
// a[j]%=m;
}
}
else if(t==4) {
int sum = 0;
for(long j=x;j<=y;j++) {
sum+=a[j];
sum%=m;
}
cout<<sum;
}
}
return 0;
}
@shivam312 the only problem is that it is very slow. Suppose if we have 1000 queries and in each query we have L=1 and R=1000 than we u can see that nit will take a lot of time in doing computation. So thats why u get TLE.
Amazing problem! I did it after reading the editorial. It took a while; but it really reinforced my understanding of segment trees. You can view my solution here if interested.
I am getting WA
https://www.codechef.com/viewsolution/7492057
I am also getting WA on similar spoj problem SPOJ.com - Problem HORRIBLE
My spoj solution id Sphere Online Judge (SPOJ) - Submit a solution
I am not able to figure out why i am getting WA in both problems. Please help me out?
Can someone tell me what is wrong with my solution.I did as told in the Editorial.
[JBAB5E - Online C++0x Compiler & Debugging Tool - Ideone.com][1]
Can you please check my code? What’s wrong with it?
[1]: JBAB5E - Online C++0x Compiler & Debugging Tool - Ideone.com
Very nice question to implement lazy propagation
can anybody tell me what’s wrong with my solution?
here is the solution :
[solution][1]
[1]: CodeChef: Practical coding for everyone
Before switching to segtree i did square root decomposition CodeChef: Practical coding for everyone . It worked for 1st 2nd and 4th subtask but not for 3rd subtask .
I think your code is update all the elements in the range as you are using the statement - if(st!-end)… i.e. you are not using lazy propagation. Lazy means to update when and only required, update it leaf nodes and return immediately. For details refer to SPOJ Discussion board… Also, Please indent your code for others to understand it easily…
Yes someone please explain