Language: C++

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <nmmintrin.h>
#include <emmintrin.h>
#include <wmmintrin.h>

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

#define unordered_map __fast_unordered_map
template<class Key, class Value, class Hash = std::hash<Key>>
using unordered_map = __gnu_pbds::gp_hash_table<Key, Value, Hash>;

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

using GF = uint32_t;

inline GF Add(GF a, GF b) {
  return a ^ b;
}

inline GF Mul(GF a, GF b) {
  __m128i xa = _mm_cvtsi64_si128(a), xb = _mm_cvtsi64_si128(b);
  xa = _mm_clmulepi64_si128(xa, xb, 0x00);
  uint64_t res = _mm_cvtsi128_si64(xa);
  GF hi = res >> 32;
  GF a0 = hi ^ (hi >> 25) ^ (hi >> 29) ^ (hi >> 30);
  return (GF)res ^ a0 ^ (a0 << 2) ^ (a0 << 3) ^ (a0 << 7);
}

vector<GF> base;

GF AddPositionsUpTo(LL x, LL y, LL max_val);
GF AddPositionsFrom(LL x, LL y, LL min_val);

map<pair<LL, LL>, GF> memo;
GF AddPositions(LL x, LL y, int bb = 60) {
  if (x == 0 && y == 0) { return 1; }
  debug("?Any", x, y);
  
  pair<LL, LL> p{x, y};
  if (memo.count(p)) { return memo[p]; }

  int bit = bb;
  while ((1LL << bit) > x + y) { --bit; }
  if (x >= (1LL << bit)) {
    GF ans = Mul(base[bit], AddPositions(x ^ (1LL << bit), y));
    debug(x, y, ans);
    return memo[p] = ans;
  }

  // x < 2^bit <= x + y
  GF answer1 = AddPositionsUpTo(x, y, (1LL << bit) - 1);
  GF answer2 = AddPositionsFrom(x, y, (1LL << bit));
  debug(x, y, answer1, answer2);
  return memo[p] = Add(answer1, answer2);
}

GF GetValue(LL x) {
  static map<LL, GF> val_memo;
  auto it = val_memo.find(x);
  if (it != val_memo.end()) { return it->nd; }

  GF ans = 1;
  for (int bit = 60; bit >= 0; --bit) {
    if ((x >> bit) & 1) {
      ans = Mul(base[bit], ans);
    }
  }
  debug("Value", x, ans);
  return val_memo[x] = ans;
}

GF AddPositionsUpTo(LL x, LL y, LL max_val) {
  debug("?UpTo", x, y, max_val);
  if (x > max_val) { return 0; }
  if (x + y <= max_val) { return AddPositions(x, y); }
  const LL orig_x = x, orig_y = y;

  GF answer = 0;
  for (int bit = 60; bit >= 0; --bit) {
    if (!((y >> bit) & 1)) { continue; }
    const LL v = 1LL << bit;
    y ^= v;

    if (x + v - 1 <= max_val) {
      debug("UpTo", orig_x, orig_y, max_val, x, y);
      answer = Add(answer, AddPositions(x, y));
      x += v;
    }
  }
  debug(answer);
  if (x <= max_val) { answer = Add(answer, GetValue(x)); }
  return answer;
}

GF AddPositionsFrom(LL x, LL y, LL min_val) {
  if (x + y < min_val) { return 0; }
  if (x >= min_val) { return AddPositions(x, y); }
  const LL orig_x = x, orig_y = y;

  GF answer = 0;
  for (int bit = 60; bit >= 0; --bit) {
    if (!((y >> bit) & 1)) { continue; }
    const LL v = 1LL << bit;
    y ^= v;

    if (x + v >= min_val) {
      answer = Add(answer, AddPositions(x + v, y));
    } else {
      x += v;
    }
  }
  debug("From", orig_x, orig_y, min_val, answer, x);
  if (x >= min_val) { answer = Add(answer, GetValue(x)); }
  return answer;
}

GF GetRandom() {
  GF ans = 0;
  for (int i = 0; i < 4; ++i) {
    ans <<= 16;
    ans |= (rand() % (1 << 16));
  }
  return ans;
}

int32_t main() {
#ifndef LOCAL
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
#endif

#ifdef TESTING
  while (true) {
    GF a = GetRandom(), b = GetRandom(), c = GetRandom();
    GF d = Mul(a, Add(b, c));
    GF e = Add(Mul(a, b), Mul(a, c));
    debug(a,b,c,d,e);
    assert(d == e);
  }
#endif

  srand(2137);

  const int S = 58;
  const LL kLarge = 1LL << S;
  for (int i = 0; i < 70; ++i) {
    GF x = GetRandom();
    base.PB(x);
  }
  debug(base);

  int N;
  cin >> N;
  vector<pair<LL, LL>> values;

  auto TotalGF = [&](LL bound) {
    GF ans = 0;
    for (auto &val : values) {
      ans = Add(ans, AddPositionsUpTo(val.st, val.nd, bound));
    }
    debug(bound, ans);
    return ans;
  };

  for (int i = 0; i < N; ++i) {
    LL x, y;
    cin >> x >> y;
    values.emplace_back(x + kLarge, y + kLarge);
  }

  debug(values);

  LL Lzero = 0, Rzero = (1LL << (S + 2));
  while (Rzero - Lzero > 1) {
    const int midzero = (Lzero + Rzero) / 2;
    if (TotalGF(midzero) == 0) {
      Lzero = midzero;
    } else {
      Rzero = midzero;
    }
  }

  const LL first_x = Rzero - kLarge;
  
  Lzero = first_x + kLarge - 2; Rzero = (1LL << (S + 2));
  const GF aim = TotalGF(Rzero);

  while (Rzero - Lzero > 1) {
    const int midzero = (Lzero + Rzero) / 2;
    if (TotalGF(midzero) == aim) {
      Rzero = midzero;
    } else {
      Lzero = midzero;
    }
  }

  const LL last_x = Rzero - kLarge;

  cout << first_x << " " << last_x - first_x - kLarge << "\n";
}



Compiler output:
In file included from a.cc:5:
a.cc: In function 'GF Mul(GF, GF)':
a.cc:61:8: error: '__builtin_ia32_pclmulqdq128' needs isa option -mpclmul -msse2
   61 |   xa = _mm_clmulepi64_si128(xa, xb, 0x00);
      |        ^~~~~~~~~~~~~~~~~~~~