Similar code getting different verdict, can someone help me out?
Can you explain your approach a bit more?
Yes, there were many square root dec submissions which passed.
I have used Segment tree and Lazy Propagation approach but I am getting TLE. Can u please tell me what improvement can be done as it is also having same time complexity. I think clearing the map everytime is resulting in TLE, How can I improve that?
say we have similarity for a block calculated (for initial position, we can manually calculate).
After update, two border blocks can be updated naively and middle blocks all will have same value, so, we can calculate for each block range using binary search or Merge sort tree as explained above.
actually i am asking do we have to store array A in (range,value) manner always or we can handle updates in any other way …(thanx …)
We use coordinate compression on array B.
@siddhant22 bro i am also facing same problem with similar kind of logic… in one case getting Runtime error… ur issue resolved?
As i know, admin is looking into this matter as this was already reported.
@huzaifa242 bro same problem i am facing…same solution submitted in giving diff time giving differt output behaviour with runtime errro… different different attemp with exact same line of code giving different output
Not Yet… Got a very different result after resubmission(CodeChef: Practical coding for everyone) with minor changes. The one test that was not passed earlier is passed now but other cases now have Wrong answer. So, it seems like my code has some undefined behaviour(maybe something like segmentation fault that is not detected).
Also, another resubmission(CodeChef: Practical coding for everyone) with additional conditions 'and’ed in assert converts the SIGABRT in my original submission to a WA which is also weird.
@boost_insane :
1)both build and update are recursive. You can try making it with loops instead for saving function call overhead.
2)(minor effect) change line 80 to: tree[right] = tree[pos] - tree;
[@siddhant22] 1 There is surely some problem with the input file of this problem changing the input format is resulting in different outputs, If you get the answer correct do comment your correct solution link.
@tihorsharma123 here you go:
- split array in sqrt(N) blocks (smaller A and B)
- for a block compute the sim of A and B & the map of frequencies for B
- updates can affect 3 types of areas
3.1) a part of the block containing left
3.2) some full blocks
3.3) a part of the block containing right - for partial block queries just update A and in the same time compute sim
- for full block just mark that block of having only value C and compute the new sim as being the count of C in the B of the block
- partial update on a block having only C -> need to fill the A array
1 Like
i used the full array but with some sort of lazy propagation(do not actually fill it until you get a partial query on that block)
@siddhant22 @boost_insane i think issue resolved now… my same solution now got AC … try to resubmit your solutions
i dont understand what is wrong in my code?
i have used segment tree with lazy prop. but a
single testcase does not get A.C .
but on my all the inputs code gives right answer??
so pls give me any good testcase !!
link to my code is: CodeChef: Practical coding for everyone
thanks !! in advance
This is almost exactly what I’ve done. I’ve used two segment trees, one for each array. The one for the second array is static while for the first I’ve done what you did. And the rest is the same.
My all testcases are passing except two, and on \text{-Ofast} g++ optimization one more test case passes. The other one is still on TLE. I feel \mathcal{O}(N\log^2 N) should pass, yet mine is failing. Well, admittedly my code is clumsy but still…