FILL THE MATRIX:-
For 100 points u need to do it O(n) or O(n logn).The inputs are as a,b,c. So there lies three conditions
1)if a=b then c has to be 0, since the same index cannot have a difference of 1.
2) if a=b and b=a , suppose 1 2 1 then 2 1 0 , both c cannot be different since |a[J]-a[I]|.
3) if a and b has already been used , you need to think in such a way that the diff is same as given when its used somewhere else.
For this you can create a 1-d matrix of n length initialized to 0 everywhere, where 0 means untouched , the other values can be 1 and 2 as the diff can never be greater then 1 as mentioned in the question.
So lets solve it offline , store the queries first and sort them , while storing just check if a=b then c=0. And while storing make sure a<b , if not swap and store them.
So now iterate through the queries from top to bottom , and there will be 4 conditions.
1) visited and visited , if both have already been visited , then their difference has to be only C else its wrong.
2)unvisited and unvisited , then make one other 1+c,
3)visited and unvisited , in this there will be two conditions , since if visited ==2 then the unvisited will become 2-c , and if visited==1 then unvisited cannot be 0 , since its visited so it will become 1+c.
4)unvisited and visited , in this there will be two conditions , since if visited ==2 then the unvisited will become 2-c , and if visited==1 then unvisited cannot be 0 , since its visited so it will become 1+c.
In this way only the 1st condition if contradicts then âNOâ else âYESâ.
The link of solution.
http://ide.geeksforgeeks.org/tVcHaf
SEREJA AND COMMANDS:-
For a 50 marks solution , you just can simply use memoization and do.
Let explain the 1st test case to make you guys more clear.
1 1 2 0
1 4 5 0
2 1 2 0
2 1 3 0
2 3 4 0
So store the queries and solve offline, start form bottom to up , and memoize how many times each command is executed rather then executing each command for increasing that will fetch you 20 points, just start form the last command and proceed as further .
1 1 2 0
1 4 5 0
2 1 2 1
2 1 3 1
2 3 4 1
In the next step when you do it will be the 2nd last command it will become 1+1 and the same value will be added to 1-3 range since if 2nd last command executes for n times then the range within it will also be executed n times .
1 1 2 2
1 4 5 2
2 1 2 3
2 1 3 2
2 3 4 1
The next step-
1 1 2 6
1 4 5 6
2 1 2 4
2 1 3 2
2 3 4 1
The next step-
1 1 2 6
1 4 5 7
2 1 2 4
2 1 3 2
2 3 4 1
the last step-
1 1 2 7
1 4 5 7
2 1 2 4
2 1 3 2
2 3 4 1
So again iterate through the queries from 1-m and then increase , this will fetch you 50 marks, since O(n^2).
For 100 marks apply the same logic just use lazy propagation to update and queries to find out how many times each command is executed.
If you donot know segment tree refer here http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html or https://www.youtube.com/watch?v=ZBHKZF5w4YU
The solution of 50 marks https://www.codechef.com/viewsolution/15228394
The solution for 100 marks using lazy trees https://www.codechef.com/viewsolution/15388053
NOT:- USE MOD PROPERLY EVERYWHERE YOU DO ADDITIONS.
