Блог пользователя AntiLeaf

Автор AntiLeaf, история, 7 лет назад, По-английски

I'm sorry to have delayed posting this entry for about an hour, and that Codeforces Round #464(Div.2) is beginning soon after this contest.

The address of the contest is here. Take part if you're willing to do some "exercise".

I regret to say that the statements are provided in Mandarin. You can use google translate for translation if necessary.

That's all. Thanks for your attention.

UPD: I've completed the English version of the editorial. Click here to have a look.

  • Проголосовать: нравится
  • +29
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Auto comment: topic has been updated by AntiLeaf (previous revision, new revision, compare).

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Is the idea for the second problem to use map of counts in a segment tree and then binary search on the answer index? I think the segment tree should be amortized log n per query, because each segment is written over at most once, and if it is a bigger segment, then the smaller ones it contains only do one rewrite. I went to sleep before actually trying it (also because I had no idea what the XOR part of the problem input was asking, google translate and my limited skill couldn't help me).

edit: after busting 4 hours on this algorithm it's still too slow for the strict 1200 ms limit (unordered_map snail life, I guess). Looks like it's time to learn this "split-merge-treap"

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

    The standard solution is using split-merge-treap.
    You can prove that the total complexity for modify is .
    Maintain split-merge-treaps for every color,and the other query can be solved in complexity.

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Thank you!

      By the way, how can you submit answer after contest end? I registered account but couldn't find any way to do so...

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        Emmm.
        I think there is a button called "转到题库" on the top,that means you can practice there after the contest end.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How do you update the treaps based on what's in the interval? I can't think of how to only choose the treaps in the interval.

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Split the interval into some continuity intervals with the same color.
        Force modify every continuity interval,split them from the original color treap and merge them to the new color treap.
        Because there is no other type of modifications,so it's not difficult to prove that the complexity is .

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I regret to say that the standard program is using just segment tree, not split-merge Treap.

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Auto comment: topic has been updated by AntiLeaf (previous revision, new revision, compare).