558D - Guess Your Way Out! II

「[x,y] の区間に含まれている」という条件から区間を絞るのは簡単なんだけど、「[x,y]に含まれていない」という条件から区間を絞るのは大変。(区間が分割されてしまう可能性があるから。)
下のコードは他の人のものを参考にした。含まれていないという条件を最後に平面捜査で判定している。
途中でいろんな条件判定を入れると data not sufficient と cheated と判定ミスをしそうなんで、うまいやり方だなぁと思った。
2*(2*(..(2*r+1)..+1)+1 を (r+1)*(2^i)-1 みたいに書ける(らしい。自分で数式といてないけど冪数列の和の公式をあてはめるとなりそう)。これで O(q*h) -> O(q) にできる。
n_exit を long long でもたせないでバグった。こういうつまらないミスを減らしたい。

class Div2D {
public:
    void solve(void) {
            int H, Q;
            cin>>H>>Q;

            ll L = (1LL<<(H-1));
            ll R = (1LL<<H)-1;

            ll ml,mr;
            ml = L;
            mr = R;

            vector<pair<ll,ll>> segs;
            // O(q)
            REP(ii, Q)
            {
                int i, ans;
                ll  l,r;
                cin>>i>>l>>r>>ans;
                // l,r を leaf(level=H) での range に変換する
                // loop を使わず書ける (O(H) -> O(1))
                l = l*(1LL<<(H-i));
                r = (r+1)*(1LL<<(H-i))-1;

                if (ans)
                {
                    // 区間の intersect で更新しておく
                    ml = max(ml, l);
                    mr = min(mr, r);
                }
                else
                  segs.emplace_back(l,r);
            }

            // intersect 済みの区間の外側を登録
            segs.emplace_back(1,ml-1);
            segs.emplace_back(mr+1,R+1);
            sort(RANGE(segs));

            // O(q)
            ll n_exit = 0;  // 最大 (2^50)/2 程度の大きさになるので long long じゃないとダメ
            ll exit = -1;
            ll rr = L-1;
            // 平面捜査
            // | ------------------------------------>
            // |[l1,r1] [l2,r2]          [l4,    r4]
            // |          [l3,      r3]    [l5,r5]
            // rr
            for (auto seg : segs)
            {
                ll l, r;
                tie(l,r) = seg;
                if (l > rr+1) // ,r1]  [l2, 間に1 より長い隙間があればそこに出口がある。
                {
                    exit = l-1;
                    n_exit += l-rr-1;
                }
                rr = max(rr, r);
            }
            if (n_exit==0)
                cout<<"Game cheated!"<<endl;
            else if (n_exit > 1)
                cout<<"Data not sufficient!"<<endl;
            else
                cout<<exit<<endl;
    }
};