cadmiumky's blog

By cadmiumky, 6 months ago,

Author: Gheal

Solution
Code

103449B — Antigo

Author: cadmiumky

Solution
Code

103449C — Find Set

Author: Hidden for their safety

Solution
Code

103449D — Updating Inversions

Author: Gheal

Solution
Code 1 (SQRT decomposition)
Code 2 (Fenwick + Bitwise Trie)

Author: Gheal

Solution
Code 1 (DP)
Code 2 (Greedy)

Author: tibinyte

Solution
Code

Author: Gheal

Solution
Code

103449H — Autumn

Author: cadmiumky

Solution
Code
damn it!

• +25

 » 5 months ago, # |   +5 Auto comment: topic has been updated by cadmiumky (previous revision, new revision, compare).
 » 5 months ago, # |   -10 Great contest! The problems are very interesting. Hope to participate again next time!
•  » » 5 months ago, # ^ |   +11 Thank you! Glad you liked our problems!
•  » » » 5 months ago, # ^ |   -8 Problem F is very classic problem. The same problem as bzoj 5125 (a Chinese Online Judge). That's only the bad thing, i think.
•  » » » » 5 months ago, # ^ |   +13 Well that problem was more like an educational problem, its purpose being the understanding of divide and conquer optimisation rather than being a challenge. That's why we decided to give it to this training round and not in official rounds.
 » 3 months ago, # |   0 I can't understand, in problem H, why you are doing updates on rnode[v] not in lnode[v]?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 It doesn't really matter, updates could've might as well be done on lnode. Really, it's correct either way because of the properties that trees imply, i.e. any segment bounded by the lnode and rnode of some vertex is completely included in another such segment if the node denoting the latter segment is an ancestor of the original vertex, otherwise these seents are completely disjoint. Therefore, any ancestor segment still includes both lnode and rnode (therefore as long as we always update a node strictly only rnode or lnode everything is correct)