Submission #1370623

#TimeUsernameProblemLanguageResultExecution timeMemory
1370623mohamedaabdullahXOR (IZhO12_xor)C++17
100 / 100
97 ms56612 KiB
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define int long long
#define endl "\n"
#define pii pair<int,int>
#define cinAll(a) for (auto &it : a) cin >> it
#define NO  void(cout << "NO\n")
#define YES void(cout << "YES\n")

// constexpr int oo = 2e18;
// constexpr int N = 1e5 + 5;
// constexpr int mod = 1e9 + 7;
// int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
// int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
// char di[] = {'D', 'U', 'R', 'L'};
int l_ans = 0, k_ans = 0;
struct Node {
    Node*bit[2];
    int l;
    Node() {
        bit[0] = bit[1] = 0;
        l = 2e18;
    }
};

struct BT {
    Node*root = new Node();

    void insert(const int &n,int index) {
        Node*curr = root;
        curr->l = min(curr->l, index);
        for (int i = 29;i >= 0;i--) {
            bool idx = (n>>i)&1;
            if (curr->bit[idx] == 0) {
                curr->bit[idx] = new Node();
            }
            curr = curr->bit[idx];
            curr->l = min(curr->l, index);
        }
    }

    int qry(int n, int x) {
        Node*curr = root;
        int best = 2e18;
        for (int i = 29;i >= 0;i--) {
            bool b1 = (n>>i)&1, b2 = (x>>i)&1;
            if (b2 == 0) {
                if (curr->bit[1^b1] != 0) {
                    best = min(best, curr->bit[b1^1]->l);
                }
                if (curr->bit[b1] != 0) curr = curr->bit[b1];
                else return best;
            }
            else {
                if (curr->bit[1^b1] != 0)
                    curr = curr->bit[1^b1];
                else return best;
            }
        }
        if (curr) best = min(best, curr->l);
        return best;
    }
};

void solve() {
    int n, x, pref = 0, l, k;
    BT t;
    t.insert(0, 0);
    cin >> n >> x;
    for (int r = 1,a;r <= n;r++) {
        cin >> a;
        pref ^= a;
        l = t.qry(pref, x);
        k = r - l ;
        if (k > k_ans) {
            k_ans = k;
            l_ans = l+1;
        }
        t.insert(pref, r);
    }
    cout << l_ans << ' ' << k_ans;
}

signed main() {
    //============================================================================
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // onlinejudge();
    //============================================================================
    int T{1};
    //cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...