Link-Cut Пельмени

#include <bits/stdc++.h>
using namespace std;
using vbo = vector<bool>;
using ll = long long;
using pll = pair<ll, ll>;
using ld = long double;
using qll = queue<ll>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using qld = queue<ld>;
using vld = vector<ld>;
using qpll = queue<pll>;
using vpll = vector<pll>;
#define watch(x) clog << #x << " equals " << x << endl;
#define all(value) value.begin(), value.end()
#define fo(XX, X, fi) for(ll XX = X; XX < fi; XX++)
#define forr(XX, X, fi) for(ll XX = X; XX <= fi; XX++)
#define roff(XX, X, fi) for(ll XX = X; XX >= fi; XX--)
ostream& endl(ostream& os) {
    return os << '\n';
}
#define vv(type,name,n,...) vector<vector<type>> name(n,vector<type>(__VA_ARGS__))
#define vvv(type,name,n,m,...) vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__)))
#define vvvv(type,name,n,m,k,...) vector<vector<vector<vector<type>>>> name(n,vector<vector<vector<type>>>(m,vector<vector<type>>(k, vector<type>(__VA_ARGS__))))
#define vvvvv(type,name,n,m,k,l,...) vector<vector<vector<vector<vector<type>>>>> name(n,vector<vector<vector<vector<type>>>>(m,vector<vector<vector<type>>>(k, vector<vector<type>>(l, vector<type>(__VA_ARGS__)))))
#define LL(...) \
  ll __VA_ARGS__; \
  IN(__VA_ARGS__)
#define fi first
#define se second
template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); }
template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); }
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& A) {
    os << A.fi << " " << A.se;
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& A) {
    for (size_t i = 0; i < A.size(); i++) {
        if(i) os << " ";
        os << A[i];
    }
    return os;
}
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T, class S> void scan(pair<T, S> &p) { scan(p.first), scan(p.second); }
template <class T> void scan(vector<T> &a) {for(auto &i : a) scan(i);}
template <class T> void scan(T &a) { cin >> a; }
void IN() {}
template <class Head, class... Tail> void IN(Head &head, Tail &...tail) {
    scan(head);
    IN(tail...);
}
void print() {
    cout << "\n";
}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(Tail)) cout << " ";
    print(forward<Tail>(tail)...);
}
#ifdef LOCAL
#include <algo/debug.h>
#else
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math,trapv")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math")
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> distrib(0ll, 1e9);
constexpr ll MOD = 1e9+7;
//constexpr ll MOD = 1e9+7;
void in(vector<ll> & a) {
    for (auto & x : a) cin >> x;
}
void in(vector<ll> & a, ll l, ll r) {
    for (ll i=l; i < r; i+=1) {
        cin >> a[i];
    }
}
void inn(vector<ll> & a, ll l, ll rr) {
    for (ll i=l; i <= rr; i+=1) {
        cin >> a[i];
    }
}
ll powm(ll a, ll b) {
    assert(b >= 0);
    ll d = 1;
    while (b) {
        if (b&1) d = (d*a) % MOD;
        b >>= 1;
        a = (a*a) % MOD;
    }
    return d;
}
ll powm(ll a, ll b, ll MOD) {
    assert(b >= 0);
    ll d = 1;
    while (b) {
        if (b&1) d = (d*a) % MOD;
        b >>= 1;
        a = (a*a) % MOD;
    }
    return d;
}
ll poww(ll a, ll b) {
    assert(b >= 0);
    ll d = 1;
    while (b) {
        if (b&1) d = (d*a);
        b >>= 1;
        a = (a*a);
    }
    return d;
}
ld poww(ld a, ll b) {
    assert(b >= 0);
    ld d = 1;
    while (b) {
        if (b&1) d = (d*a);
        b >>= 1;
        a = (a*a);
    }
    return d;
}
ll mul(ll a, ll b) {
    return (a*b)%MOD;
}
ll sum(ll a, ll b) {
    return (a+b)%MOD;
}
ll sub(ll a, ll b) {
    return (a-b+100*MOD)%MOD;
}
ll fj0dsq983gf8(ll index, vector<ll> & tree)  {
    index += 1;
    ll sum = 0;
    while (index > 0) {
        sum += tree[index-1];
        index -= index & -index;
    }
    return sum;
} // zero-indexed!!!
ll get_sum_ft(ll left, ll right, vector<ll> & tree) {
    ll n = (ll)tree.size();
    if (!(left <= right)) return 0;
    assert(left <= right);
    if (right >= n) {
        clog << "FENWICK ALERT: R >= tree.size() (IT'S ZERO INDEXED !!!)" << endl;
        right = n-1;
    }
    ll ans = fj0dsq983gf8(right, tree);
    if (left-1 >= 0) {
        ans -= fj0dsq983gf8(left - 1, tree);
    }
    return ans;
} // zero-indexed!!!
void inc_ft(ll index, ll inc, vector<ll> & tree) {
    ll n = (ll)tree.size();
    assert(index >= 0);
    assert(index < n);
    index += 1;
    while (index < n) {
        tree[index] += inc;
        index += index & -index;
    }
} // zero-indexed!!!
void build_ft(vector<ll> & a, vector<ll> & tree) {
    ll n = (ll)tree.size();
    assert(tree.size() == a.size());
    for (ll i = 0; i < n; i++) {
        tree[i] += a[i];
        ll r = i | (i + 1);
        if (r < n) tree[r] += tree[i];
    }
} // zero-indexed!!!
ll inv(ll i, ll m) {
    if (i == 1) return 1; return m-((inv(m%i, i)*m)/i);
}
/*
void copy_this () {
    ll n; cin >> n;
    ll n, k; cin >> n >> k;
    ll n, q; cin >> n >> q;
    ll a[n]; for (ll i=0; i < n; i+=1) cin >> a[i];
    vector<ll> a(n); for (ll i=0; i < n; i+=1) cin >> a[i];
}
*/
void solve() {
    ll l = 0;
    ll r;
    cin >> r;
    vvvvv(pll, dp, 61, 2, 2, 2, 2, make_pair(0ll, 0ll));
    unordered_map<ll, ll> cnt;
    // dp[бит][x уже больше l][x уже меньше r][y уже больше l][y уже меньше r]
    function<pll(ll, ll, ll, ll, ll)> count = [&](ll i, ll xl, ll xr, ll yl, ll yr) {
        if (i < 0) return make_pair(0ll, 1ll);
        if (dp[i][xl][xr][yl][yr] != make_pair(0ll, 0ll)) return dp[i][xl][xr][yl][yr]; // alrhvebeencalced
        ll res = -1e9;
        ll rescnt = -1e9;
        ll lefthas0 = !((1ll << i)&l);
        ll righthas0 = !((1ll << i)&r);
        ll lefthas1 = ((1ll << i)&l);
        ll righthas1 = ((1ll << i)&r);
        vll ithbitofx;
        vll ithbitofy;
        if (lefthas0 || xl) {
            // у икса может быть выключен iый бит
            ithbitofx.push_back(0);
        }
        if (righthas1 || xr) {
            // у икса может быть включен iый бит
            ithbitofx.push_back(1);
        }
        if (lefthas0 || yl) {
            // у игрека может быть выключен iый бит
            ithbitofy.push_back(0);
        }
        if (righthas1 || yr) {
            // у игрека может быть включен iый бит
            ithbitofy.push_back(1);
        }
        for (const auto &xi : ithbitofx) {
            for (const auto &yi : ithbitofy) {
                ll addition = ((xi|yi) << (i));
                ll nxl = xl;
                if (xi && lefthas0) {
                    nxl = 1;
                }
                ll nxr = xr;
                if (!xi && righthas1) {
                    nxr = 1;
                }
                ll nyl = yl;
                if (yi && lefthas0) {
                    nyl = 1;
                }
                ll nyr = yr;
                if (!yi && righthas1) {
                    nyr = 1;
                }
                pll go = count(i-1, nxl, nxr, nyl, nyr);
                if (go.first+addition > res) {
                    res = go.first+addition;
                    rescnt = go.second;
                } else if (go.first+addition == res) {
                    rescnt = sum(rescnt, go.second);
                }
            }
        }
        return dp[i][xl][xr][yl][yr]=make_pair(res, rescnt);
    };
    pll my_ans = count(60,0,0,0,0);
    cout << 2*my_ans.first << " " << my_ans.second << endl;
}

int32_t main(int32_t argc, char* argv[]) {
    cout << setprecision(17);
    bool use_fast_io = true;
    for (int32_t i = 1; i < argc; ++i) {
        if (string(argv[i]) == "-local-no-fast-io") {
            use_fast_io = false;
//            cout << "No fastIO" << endl;
            break;
        }
    }
    if (use_fast_io) {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        cerr.tie(nullptr);
        clog.tie(nullptr);
    }
    ll tt = 1;
//    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}