結果

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

ソースコード

diff #
raw source code 

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


constexpr int E = 40;
Int easy[E + 1];

Int solve(Int L, Int R) {
  vector<pair<int, Int>> ps, qs;
  {
    Int l = L, r = R;
    for (int e = 0; l < r; ++e) {
      if (l & 1LL << e) {
        ps.emplace_back(e, l);
        l += (1LL << e);
      }
      if (r & 1LL << e) {
        r -= (1LL << e);
        qs.emplace_back(e, r);
      }
    }
    assert(l == r);
  }
  Int ans = 0;
  for (int i = 0; i < (int)ps.size(); ++i) {
    ans += easy[ps[i].first];
    if (i) ans += (1LL << ps[i].first);
  }
  for (int i = 0; i < (int)qs.size(); ++i) {
    ans += easy[qs[i].first];
    if (i) ans += (1LL << qs[i].first);
  }
  if (ps.size() && qs.size()) {
    Int mn = 1LL << E;
    for (const auto &p : ps) for (const auto &q : qs) {
      const int e = max(p.first, q.first);
      Int x = p.second ^ q.second;
      x &= ~((1LL << e) - 1);
      chmin(mn, x);
    }
    ans += mn;
  }
  return ans;
}

int main() {
  for (int e = 0; e < E; ++e) {
    easy[e + 1] = 2 * easy[e] + (1LL << e);
  }
cerr<<"easy = ";pv(easy,easy+(E+1));
  // exper(); return 0;
  
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    Int N, M;
    scanf("%lld%lld", &N, &M);
    const Int L = M;
    const Int R = M + N;
    const Int ans = solve(L, R);
    printf("%lld\n", ans);
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}
0