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

Can someone help me with this problem?
Автор atkiya, история, 16 месяцев назад, По-английски

I'm getting TLE for my solution of this 616D - Longest k-Good Segment problem and here's my solution link: https://ideone.com/fork/mFxA7g How can I fix this? Also, here's my submission link: 219228830

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

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

This code is O(N^2) i think

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

.

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

    Okay. Thanks! But can you please tell me how can I solve this problem without set?

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

      You are using set only to count the current number of unique numbers in the segment right?

      Replace set with a variable countCurrent.

      Replace s.insert(a[i]); with if(!m[a[i]]) countCurrent++;

      Similarly, replace if(!m[a[j]])s.erase(a[j]); with if(!m[a[j]]) countCurrent--;

      I hope it helps.

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

    Doesn't size() work in O(1)?

    → Ответить