Submission #1140871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140871		samy_nagy	XOR (IZhO12_xor)	C++20	0 / 100	0 ms	320 KiB

xor

#include <bits/stdc++.h>
/// لتكن مشيئتك
#define int long long
#define ll long long
using namespace std;
const int N = 1e3 + 5, mod = 1e9 + 7;// 1e9+7, 998244353
struct SegTree {
#define LF (x*2+1)
#define RT (x*2+2)
#define md ((lx+rx) >> 1)
    vector<int> seg;
    vector<int> lazy;
    int ignoreValue;
    int sz;

    SegTree(int n, vector<pair<int, int>> &a) {
        sz = 1;
        while (sz < n)sz *= 2;
        ignoreValue = 0; /// update this
        seg.assign(4 * n, ignoreValue);
        build(a);
    }

    void build(vector<pair<int, int>> &a, int x = 0, int lx = 0, int rx = -1) {
        if (rx == -1)rx = sz - 1;
        if (lx == rx) {
            if (lx < a.size()) {
                seg[x] = a[lx].second;
            }
            return;
        }
        build(a, LF, lx, md);
        build(a, RT, md + 1, rx);
        seg[x] = merge(seg[LF], seg[RT]);

    }

    int merge(const int &lf, const int &rt) {
        return max(lf, rt); /// update this
    }

    int query(int l, int r, int x = 0, int lx = 0, int rx = -1) {
        if (rx == -1)rx = sz - 1;
        if (l <= lx and rx <= r) {
            return seg[x];
        }
        if (r < lx or rx < l) {
            return ignoreValue;
        }
        return merge(
                query(l, r, LF, lx, md),
                query(l, r, RT, md + 1, rx)
        );
    }

#undef md
#undef LF
#undef RT
};

void solve() {
    int n, x;
    cin >> n >> x;
    vector<pair<int, int>> pref;
    int c{};
    for (int i = 0; i < n; ++i) {
        int u;
        cin >> u;
        c ^= u;
        pref.emplace_back(c, i);
    }
    std::sort(pref.begin(), pref.end());
    if (!x) {
        cout << 1 << " " << n;
        return;
    }
//    for (auto [l, r]: pref)cout << l << " " << r << endl;
    SegTree tree(n, pref);
    auto get = [&](int tar, int ed) -> pair<int, int> {
        /// Range prefR
        int L = 0, R = 0;
        for (int i = 30; i >= ed; --i) {
            if ((tar >> i) & 1) {
                L |= (1ll << i);
                R |= (1ll << i);
            }
        }
        R |= (1ll << ed) - 1;
        int l = lower_bound(pref.begin(), pref.end(), make_pair(L, 0ll)) - pref.begin();
        int r = upper_bound(pref.begin(), pref.end(), make_pair(R - 1, 0ll)) - pref.begin();
        if (l > r)return {0, 0};
        if (r == n)r--;
//        cout << tar << " " << ed << endl;
//        cout << L << " " << R << " " << l << " " << r << endl;
        /// PrefL
        pair<int, int> ret = {-1, -1};
        int end = tree.query(l, r);
//        cout << end << endl;
        for (int j = 0; j < n; j++) {
            bool ok = 1;
            for (int i = 30; i >= ed; --i) {
                if (((tar >> i) & 1)) {
                    ok &= (((pref[j].first >> i) & 1) == 0);
                }
            }
            if (ok) {
                int st = pref[j].second;
                if (st > end)swap(st, end);
//                cout << st << " " << l << " " << r << " " << end << endl;
                ret = max(ret, {end - st + 1, st + 1});
            }
        }


        return ret;
    };
    pair<int, int> ans = {-1, -1};/// k , i
    int i;
    for (i = 30; ~i; --i) {
        if ((x >> i) & 1) {
            break;
        }
    }
    for (int j = 0; j <= 30; ++j) {
        if ((x >> j) & 1) {
            ans = max(ans, get(x, (j)));
            break;
        }
    }

    for (; ~i; --i) {
        if (!((x >> i) & 1)) {
            int tar = x | (1ll << i);
            ans = max(ans, get(tar, i));
        }
    }
    cout << ans.second << " " << ans.first ;

}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);



    int tc = 1;
    // cin >> tc;
    for (int i = 1; i <= tc; ++i) {
        solve();
        //  cout << "\n";

    }
}

• Subtask 1: 0 / 100