@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.
Can this problem be done in O(N^2) time?
Here’s my solution with seg tree + lazy propagation - https://www.codechef.com/viewsolution/20402757
@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