ques : ABX03 Problem - CodeChef
my solution : CodeChef: Practical coding for everyone
I have done it using persistence segment trees but it is giving RE for 2nd subtask. Please provide a counter case!
The main reason is:
See u are actually constructing segment tree dynamically,i.e u only make the node which are required.So if any range comes such that u haven’t made a node for it,it’ll cause RE.
I am talking about your query part.
Eg test case:
Input:
3 2
1 2 6
1 3 11
2 3 1000 1001 3 20 2 4
-4 -3 -4 14 -3 -1 -4 -2
Leave runtime error, but for some reason your code gives wrong output for this case-
Input
5 1
1 2 6
2 3 6
4 3 6
5 2 9
1 3 1 10 1 10 1 10
Your Output
6
Expected Output
12
1 Like
You could see this implementation if u want:
https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/
i have made trees for all the n nodes during dfs(as it will iterate to all the nodes)
in this case output of first will be 0 and for next the (u, v) = (-4, -3). Is it allowed?
Ooh sorry!! I didnt see ur build first function
I’ll see if i can find any error
No problem. Thanks for looking into my code!
I dont know if this will help u or not.But your ans is coming wrong due to which conditions like u<0 and v<0 arise which cause RE.
See this: CodeChef: Practical coding for everyone
1 Like
Thanks i had fixed it and it is now giving correct result : FOUR FRIENDS, C++ (gcc) - rextester but still RE.
: Thank you mate !
Glad about that 