結果

問題 No.3444 Interval Xor MST
コンテスト
ユーザー ococonomy1
提出日時 2026-02-06 22:38:53
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 5,749 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,035 ms
コンパイル使用メモリ 217,140 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2026-02-06 22:39:00
合計ジャッジ時間 6,971 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pli = pair<ll,int>;
#define MOD 998244353
//#define MOD 1000000007
#define el '\n'
#define El '\n'
#define YESNO(x) ((x) ? "Yes" : "No")
#define YES YESNO(true)
#define NO YESNO(false)
#define EXIT_ANS(x) {cout << (x) << '\n'; return;}
#define PA() {EXIT_ANS(ans);}
template <typename T> void inline SORT(vector<T> &v){sort(v.begin(),v.end()); return;}
template <typename T> void inline REV(vector<T> &v){reverse(v.begin(),v.end()); return;}
template <typename T> void inline VEC_UNIQ(vector<T> &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); return;}
template <typename T> T inline MAX(vector<T> &v){return *max_element(v.begin(),v.end());}
template <typename T> T inline MIN(vector<T> &v){return *min_element(v.begin(),v.end());}
template <typename T> T inline SUM(vector<T> &v){T ans = 0; for(int i = 0; i < (int)v.size(); i++)ans += v[i]; return ans;}
template <typename T> void inline DEC(vector<T> &v){for(int i = 0; i < (int)v.size(); i++)v[i]--; return;}
template <typename T> void inline INC(vector<T> &v){for(int i = 0; i < (int)v.size(); i++)v[i]++; return;}
void inline TEST(void){cerr << "TEST" << endl; return;}
template <typename T> bool inline chmin(T &x,T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}
template <typename T> bool inline chmax(T &x,T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template <typename T = long long> vector<T> inline get_vec(int n){
    vector<T> ans(n);
    for(int i = 0; i < n; i++)cin >> ans[i];
    return ans;
}
template <typename T> void inline print_vec(vector<T> &vec,bool kaigyou = false){
    int n = (int)vec.size();
    for(int i = 0; i < n; i++){
        cout << vec[i];
        if(kaigyou || i == n - 1)cout << '\n';
        else cout << ' ';
    }
    if(!n)cout << '\n';
    return;
}
template <typename T> void inline debug_vec(vector<T> &vec,bool kaigyou = false){
    int n = (int)vec.size();
    for(int i = 0; i < n; i++){
        cerr << vec[i];
        if(kaigyou || i == n - 1)cerr << '\n';
        else cerr << ' ';
    }
    if(!n)cerr << '\n';
    return;
}


vector<ll> v;

//[l1,r1] から一つ、[l2,r2] から一つ選んで、 xor の最小値はいくつになるか
ll func(ll l1,ll r1,ll l2,ll r2){
    
    if(l1 <= l2 && l2 <= r1)return 0;
    if(l1 <= r2 && r2 <= r1)return 0;
    if(l2 < r1){
        swap(l1,l2);
        swap(r1,r2);
    }
    //cerr << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << ' ';
    //l1 <= r1 < l2 <= r2
    assert(l1 == 0);
    assert(r1 < l2);

    ll ans = 0;
    for(int i = 37; i >= 0; i--){
        if(!(r2 & (1LL << i)))continue;
        // TEST();
        // cerr << (1LL << i) << el;
        if(l2 & (1LL << i)){
           l2 -= (1LL << i);
           r2 -= (1LL << i);
           ans += (1LL << i);
           if(r1 >= l2){
                //cerr << ans << el;
                return ans;
           }
           continue;
        }
        r2 = (1LL << i) - 1;
        continue;
    }
    //cerr << ans << el;
    return ans;

}

ll saiki(ll l,ll r){
    //cerr << l << ' ' << r << el;
    if(l == r)return 0;
    if(r == l + 1)return (l ^ r);
    int k = -1;
    for(int i = 37; i >= 0; i--){
        bool bl = (((1LL << i) & l) != 0);
        bool br = (((1LL << i) & r) != 0);
        if(bl == br){
            if(bl){
                l -= (1LL << i);
                r -= (1LL << i);
            }
            continue;
        }
        k = i;
        break;
    }    
    assert(k != -1);
    if(l == 0 && r == (1LL << (k + 1)) - 1){
        return v[k];
    }
    ll ans = saiki(l,(1LL << k) - 1);
    ans += saiki((1LL << k),r);
    //if(r - l >= (1LL << k))return (ans + (1LL << k));

    //[l,(1LL << k)-1], [(1LL << k),r] から1個ずつ値を選ぶとして、 xor の最小値はいくつか？
    //[0,r - (1LL << k)]
    //[l,(1LL << k)-1] から1個ずつ値を選ぶとして、 xor の最小値はいくつか？に ans + (1LL << k) を足せばよい
    //l で上から抑えられるが、もっと小さいのもあるしあんまり意味はない？
    ans += (1LL << k);
    //cerr << 0 << ' ' << r - (1LL << k) << ' ' << l << ' ' << (1LL << k) - 1 << ' ' << func(0,r - (1LL << k),l,(1LL << k) - 1,33) << el;
    ans += func(0,r - (1LL << k),l,(1LL << k) - 1);
    return ans;
}

#define MULTI_TEST_CASE true
void solve(void){
    //問題を見たらまず「この問題設定から言えること」をいっぱい言う
    //よりシンプルな問題に言い換えられたら、言い換えた先の問題を自然言語ではっきりと書く
    //複数の解法のアイデアを思いついた時は全部メモしておく
    //g++ -D_GLIBCXX_DEBUG -Wall -O2 e.cpp -o o

    //クラスカル法の気持ちになろう
    //2k,2k+1 は真っ先に繋いで良い(1)
    //次に、4k,4k+2(or 4k+1,4k+3) を繋ぎたい(2)
    //次に、8k,8k+4(or 8k+1,8k+5 or 8k+2,8k+6 or 8k+3,8k+7) を繋ぎたい(4)
    //こういう感じで logN くらいでやるしかないよなあ
    long long n,m;
    cin >> n >> m;
    
    //cerr << saiki(n,m) << el; return;
    cout << (long long)saiki(m,m + n - 1) << el;
    return;
}

void calc(void){
    v.push_back(1);
    for(int i = 1; i < 40; i++){
        v.push_back(v.back() * 2LL + (1LL << i));    
    }
    return;
}

signed main(void){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    calc();
    int t = 1;
    if(MULTI_TEST_CASE)cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
0