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

Please help in this question
Автор 650iq, история, 7 месяцев назад, По-английски

Hi everyone i was trying this question from Atcoder — https://atcoder.jp/contests/abc157/tasks/abc157_e But im getting runtime error on my code. My approach is to build a segment tree where each node contains a map of characters. And while we go up we keep on merging the maps into a single map and the return the size of the map as a answer to the query. Im not getting any WA but RE. Please help. Here is my submission https://atcoder.jp/contests/abc157/submissions/47573702

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

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

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

→ Ответить
»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hint: look at size of Tree T. is it ok?

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

    Yeah i guess making vector of map of that size would be getting memory limit exceeded.. any alternate approach or modification in my code can u suggest?

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

      What if you store the index for all characters in an array? then just a simple check of 26 times if any of them are in this range which can be easily done through binary search.

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

        Yes i know that approach but i wanted to do this with segment tree

        → Ответить