https://mirror.codeforces.com/problemset/problem/243/A Hey cfers can anyone please provide me with an simple editorial for this problem. Thank you
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
https://mirror.codeforces.com/problemset/problem/243/A Hey cfers can anyone please provide me with an simple editorial for this problem. Thank you
Name |
---|
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
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.