結果

問題 No.3444 Interval Xor MST
コンテスト
ユーザー 👑 potato167
提出日時 2025-12-28 04:57:49
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 3,516 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,932 ms
コンパイル使用メモリ 214,788 KB
実行使用メモリ 19,272 KB
最終ジャッジ日時 2026-02-06 20:50:49
合計ジャッジ時間 8,784 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1
other -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

static const unsigned long long INF = (1ULL<<62);

/*
  minxor between two intervals [l1,r1], [l2,r2] where all values are within [0, 2^(bit+1)-1].
  Returns minimum possible (x xor y).
  Greedy by highest bit: try to make current xor-bit 0 if possible.
*/
unsigned long long minxor_interval(unsigned long long l1, unsigned long long r1,
                                  unsigned long long l2, unsigned long long r2,
                                  int bit) {
    if (l1 > r1 || l2 > r2) return INF;
    if (bit < 0) return 0;

    unsigned long long half = 1ULL << bit;

    // Split interval1 into low/high parts with respect to 'half'
    unsigned long long a0l = l1, a0r = min(r1, half - 1);
    unsigned long long a1l = 0,  a1r = (unsigned long long)(-1);
    if (r1 >= half) {
        a1l = max(l1, half) - half;
        a1r = r1 - half;
    }

    // Split interval2 similarly
    unsigned long long b0l = l2, b0r = min(r2, half - 1);
    unsigned long long b1l = 0,  b1r = (unsigned long long)(-1);
    if (r2 >= half) {
        b1l = max(l2, half) - half;
        b1r = r2 - half;
    }

    unsigned long long best = INF;

    // Try xor bit = 0 first
    if (a0l <= a0r && b0l <= b0r) {
        best = min(best, minxor_interval(a0l, a0r, b0l, b0r, bit - 1));
    }
    if (a1l <= a1r && b1l <= b1r) {
        best = min(best, minxor_interval(a1l, a1r, b1l, b1r, bit - 1));
    }
    if (best != INF) return best;

    // Must take xor bit = 1
    if (a0l <= a0r && b1l <= b1r) {
        best = min(best, minxor_interval(a0l, a0r, b1l, b1r, bit - 1));
    }
    if (a1l <= a1r && b0l <= b0r) {
        best = min(best, minxor_interval(a1l, a1r, b0l, b0r, bit - 1));
    }
    return (1ULL << bit) + best;
}

/*
  MST cost for consecutive interval [L,R] with weight x xor y.
  bit is the current bit to consider; we assume values are < 2^(bit+1) and L,R are within the same block of size 2^(bit+1),
  which holds if we start with bit=31 for this problem's constraints.
*/
unsigned long long mst_interval(unsigned long long L, unsigned long long R, int bit) {
    if (L >= R || bit < 0) return 0;

    unsigned long long bL = (L >> bit) & 1ULL;
    unsigned long long bR = (R >> bit) & 1ULL;

    if (bL == bR) {
        return mst_interval(L, R, bit - 1);
    }

    // They differ at 'bit': split within the block determined by higher bits.
    unsigned long long base = (L >> (bit + 1)) << (bit + 1);
    unsigned long long end0 = base + (1ULL << bit) - 1;
    unsigned long long start1 = base + (1ULL << bit);

    unsigned long long AL = L, AR = min(R, end0);      // bit=0 side
    unsigned long long BL = max(L, start1), BR = R;    // bit=1 side

    // Lower-bit intervals (size 2^bit domain):
    // A is [AL-base, AR-base] inside [0,2^bit-1]
    // B is [BL-start1, BR-start1] inside [0,2^bit-1]
    unsigned long long aL = AL - base, aR = AR - base;
    unsigned long long cL = BL - start1, cR = BR - start1;

    unsigned long long crossLower = minxor_interval(aL, aR, cL, cR, bit - 1);
    unsigned long long cross = (1ULL << bit) + crossLower;

    return mst_interval(AL, AR, bit - 1) + mst_interval(BL, BR, bit - 1) + cross;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        unsigned long long N, M;
        cin >> N >> M;
        unsigned long long L = M;
        unsigned long long R = M + N - 1;
        cout << mst_interval(L, R, 31) << "\n";
    }
    return 0;
}
0