650iq's blog

Please help in this question
By 650iq, history, 7 months ago, In English

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

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply