### GOJO_GOKU_KURAMA's blog

By GOJO_GOKU_KURAMA, history, 4 weeks ago,

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

 » 4 weeks ago, # |   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#include using namespace std; char nl = '\n'; using i64 = long long; void solve(int t) { // cout << "test #" << t << << nl; int n; cin >> n; vector A(n); for(auto& a : A) cin >> a; // nxt[i][bit] stores the nearest position where this bit is set vector> nxt(n + 1, vector (21, n)); for(int i = n - 1; i >= 0; i--) { nxt[i] = nxt[i + 1]; for(int b = 0; b < 21; b++) { if(A[i] & (1 << b)) nxt[i][b] = i; } } // prefix or can have atmost 20 distinct values // finding distinct elemnt in all prefix i..n vector mark(int(1 << 21)); for(int i = 0; i < n; i++) { // currently on prefix i..n int cur = A[i]; int jump = i; // this while loop will run atmost 20 times while(jump < n) { cur |= A[jump]; mark[cur] = 1; /* mn is the nearest position where we get new set bit which is currently unset in prefi i..jump */ int mn = n; for(int b = 0; b < 21; b++) { if((cur & (1 << b)) == 0) mn = min(mn, nxt[jump][b]); } jump = mn; } } cout << accumulate(mark.begin(), mark.end(), 0) << nl; } int main() { int tt = 1; // cin >> tt; for(int t = 1; t <= tt; t++) solve(t); } 
•  » » 4 weeks ago, # ^ | ← 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.