HackerRank - Changing Bits

HackerRankのChanging Bitsを解いた。

AとB用にsize Nの配列を作り、setされるたびに指定indexのbitを更新する。
getのときにLSB側から愚直にA+Bを計算するとTime limit exceededになるのでA+Bの計算量を減らす工夫が必要。
ここでpythonからC++に変更。

getするindexのbitを決めるのはA[index]+B[index]だけでなく、下位bitからの繰り上がりもあるので、index部分からLSBに向かって繰り上がりがないかAとBを走査していく。A[i]とB[i]がともに１なら繰り上がりありで終了、ともに0ならなしで終了。
これでTLEは結構減るが、いくつかのテストデータはもう10%くらい処理時間を削る必要がある。

あるindex値xからLSB側に走査していき、y番目で繰り上がりあり・なしが確定して終了したとすると、
次に[x,y]内のindexがgetされた場合は、走査を省略して繰り上がりあり・なしを判断すれば計算量を減らせるので、
走査した結果をキャッシュしておくような仕組みを入れた。 ただ、このキャッシュ内にsetされると、無効化したり範囲を狭くしないとまずいのでややこしい…
これでローカルだと4倍以上速くなったが、submitしたら結構ギリギリのAcceptだった。

出題者の想定するアルゴリズムになってない気がするが、効率的な解き方があるんだろうか？？
問題名でググるとStack Overflowとか海外のブログが引っかかるけど、斬新な解き方みたいな情報は見つからなかったし、途中であきらめてる人が多いっぽい。