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

Автор GOJO_GOKU_KURAMA, история, 2 месяца назад, По-английски

https://mirror.codeforces.com/problemset/problem/243/A Hey cfers can anyone please provide me with an simple editorial for this problem. Thank you

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

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

The idea is prefix or of array the values can change atmost 20 times, so iterate over all the prefix and mark all the distinct values occuring in the prefix or. TC will be O(20 * n) or O(1e6) as there are only 1 test case

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

    I think a simpler implementation is to maintain a set of all currently possible trailing possible values of bitwise OR i.e. if we are at index i our set has all possible values of f(l, i) for l <= i, this set can never have size more than 20.