The editorial solution is O(n+m).
1 Like
You need to use modulo arithmetic when implementing BIT.
Oh right. I misread the alternative solution.
Can anyone show some light on why we need the difference array?
Thanks in advance!!
Can someone tell me whatâs wrong in my code?
I used a 2-d array to store the array after each command. The command 1 executes normally.
But for command 2, (2 l r)
the array after last executed command is added with the array after command number ârâ and then subtracted with the array before command number âlâ, hence adding the result of all the commands executing in [l, r] index to the current array.
I know using a 2-d array wonât work for higher test cases in c++, and not using a difference array would maybe take too much time but I couldnât get my program to work for even the second sub task (I got WA) while it worked fine for first sub-task. I just need to know whatâs wrong with this approach.
And just for clarity, I also tried this approach with difference array. Still didnât work.
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <inttypes.h>
using namespace std;
#define max 1000000007
int main()
{
int t;
scanf("%d", &t);
for(int i=0; i<t; i++)
{
int n, m;
scanf("%d%d", &n, &m);
int com[m][n];
memset(com, 0, sizeof(com));
for(int j=0; j<m; j++)
{
int c, a, b;
cin>>c>>a>>b;
if(c==1)
{
if(j==0)
{
com[j][a-1]++;
com[j][b]--;
}
else
{
for(int k=0; k<n; k++)
{
com[j][k]=com[j-1][k];
}
com[j][a-1]=(com[j-1][a-1]%max+1)%max;
com[j][b]=com[j-1][b]-1;
}
}
else
{
if(a<2)
{
for(int k=0; k<n; k++)
{
com[j][k]=(com[j-1][k]%max + com[b-1][k]%max)%max;
}
}
else
{
for(int k=0; k<n; k++)
{
com[j][k]=(com[j-1][k]%max + com[b-1][k]%max - com[a-2][k]%max)%max;
}
}
}
/*for(int k=0; k<n; k++)
{
printf("%d ", com[j][k]);
}
cout<<endl;*/
}
printf("%d ", com[m-1][0]);
for(int j=1; j<n; j++)
{
com[m-1][j]=(com[m-1][j]%max+com[m-1][j-1]%max)%max;
printf("%d ", com[m-1][j]);
}
printf("\n");
}
}I was getting RZEC in python while the same logic in c++ was passing the first 2 subtasksâŚ
I used that but may not be correctly
Hi ,if any one knows why submission for SEACO is not allowed now?
I coded according to the editorial only but getting WA in subtask 2 and 3, Can anyone tell me why?
Here is the link to my code -
[1]
[1]: https://www.codechef.com/viewsolution/15414725@harsh24
I have used the same approach and got 100 points. I have added explanation just above, alongwith a link to my code.
Ask me anything if requiredâŚ
Hersâs the link
Please upvote if u find that helpfulâŚ
Because the alternative is to update the actual array, which will result in O (N) complexity per command, thus O (N^2) comolexity for whole task, giving TLE.
using difference array, u apply update in constant time.
I have used difference arrays only and got 100 points. I have added explanation just above, alongwith a link to my code.
Ask me anything if requiredâŚ
Hersâs the link
Please upvote if u find that helpfulâŚ
The contest has ended.
Now submission is not allowed for contest. U may solve the question in practice section using following link
This is the contest problem link.
Just remove the contest name and ull be able to submit solutionâŚ
Following link
I saw your code . The last part of your approach is the same as mine.But I havenât yet found out the mistake in my code.Please tell me if you find any bug in my code.
Thank you
can anyone provide an easy editorial for this problemâŚ
I did this problem in a different way. I used two segment trees with lazy propagation on both of them. My solution passed in 0.30 secs.
segment tree for queries - segQ
segment tree for array - segA
First, I updated segQ with a val=1 (as every operation will be executed at least once). Then I ran a loop from m-1 to 0 and updated all the queries of type 2. Like for example for the 3rd sample test case of the problem, if the query was 2 1 5, then first I got the initial value on that node by doing query on segQ to get the no. of times this operation will be executed (say x) in future then with that value I updated the operations from 1 to 5 (i.e. l and r of the query) which means operations from 1 to 5 will be called x more times so add.
Then after that I ran a second loop from 0 to m-1 but this time for queries of type 1 and updated segA with the values for that particular command on my segQ.
This is my full code
Hii! Can u please elaborate why did u do the following steps for type 2:
if(command[i][0] == 2){
range[command[i][2]]+=t+1;
range[command[i][1]-1] -= t+1;
}
I mean I am not able to get why you add t+1 to range[command[i][2]] and subtract it from range[command[i][1]-1] and why not like you did in query of type 1!
Thanks 
If for commands we build the difference sequence in backward order, as the editorial does, but for the array we build it in forward order, then it is sufficient to just keep the running totals (without actually restoring the corresponding sum sequences).
Here is python solution.
Well, the essential point is given in the question itself,
âItâs guaranteed that r is strictly less than the enumeration/number of the current command.â
So, we run a loop in backward order, keeping track which command is to be executed how many timesâŚ
Well, a restore to actual sum sequence is required because after that, we are to provide for command type 1 also.
I have discussed my implementation in detail in the following link
Please UPVOTE if you find this helpfulâŚ
Here, variable t is keeping the track how many times this particular command is to be executed within the previously processed commands of type 2.
In the problem, we are supposed to execute all the commands exactly once, so 1 is added for that execution in third loop.
Please UPVOTE, much neededâŚ
Hope its clear nowâŚ
Feel free to ask anythingâŚ
For example N = 3, M = 3
1 1 1
2 1 1
2 1 2
initially range array 0 0 0 0
During first loop
when i == 3
t is 0
we added (t+1) = 1 to range[2]
subtracted 1 from range[1-1]
range array becomes -1 0 1 0
i == 2
t = 1 (0 + range[2])
we added (t+1) = 2 to range[1]
subtracted 2 from range[0]
range array becomes -3 2 1 0
ignore i == 1
final range array -3 2 1 0
sum array 0 3 1 0 (using reverse loop)
From here, we can ignore commands of type 2 and see, command 1 is to be executed 3 times because of other commands + 1 time for its own, as i mentioned above.
Answer array is 4 0 0
1 Like