Submission #378510

#	Time	Username	Problem	Language	Result	Execution time	Memory
378510		ijxjdjd	XOR (IZhO12_xor)	C++14	100 / 100	217 ms	91500 KiB

xor

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) std::begin(x), std::end(x)

//using namespace std;

using ll = long long;

const int MAXN = 250000 + 25;
const int MAXK = 30;
int X;
int arr[MAXN];


int left[MAXN*MAXK];
int right[MAXN*MAXK];
int mn[MAXN*MAXK];
int sz = 1;

std::pair<int, int> ans;

void updAns(int i, int j) {
    if (j-i>ans.second) {
        ans = {i, j-i};
    }
    else if (j - i == ans.second && j < ans.first) {
        ans = {i, j-i};
    }
}
void query(int i, int n=0, int b=MAXK-1) {
    if (b == -1 || n == -1) {
        return;
    }
    else {
        if ((X&(1<<b)) == 0) {
            if (arr[i]&(1<<b)) {
                if (left[n] != -1) {
                    updAns(mn[left[n]], i);
                }
            }
            else {
                if (right[n] != -1) {
                    updAns(mn[right[n]], i);
                }
            }
        }
        if ((arr[i]&(1<<b)) == (X&(1<<b))) {
            query(i, left[n], b-1);
        }
        else {
            query(i, right[n], b-1);
        }
    }
}
void add(int i, int n=0, int b = MAXK-1) {
    mn[n] = std::min(mn[n], i);
    if (b == -1) {
        return;
    }
    if (arr[i]&(1<<b)) {
        if (right[n] == -1) {
            right[n] = sz++;
        }
        add(i, right[n], b-1);
    }
    else {
        if (left[n] == -1) {
            left[n] = sz++;
        }
        add(i, left[n], b-1);
    }
}
void upd(int i) {
    query(i);
    add(i);
}
int main() {
    std::fill(all(left), -1);
    std::fill(all(right), -1);
    std::fill(all(mn), MAXN);
	std::cin.tie(0);
	std::cin.sync_with_stdio(0);
	int N;
	std::cin >> N >> X;
	X--;
	if (X == -1) {
        std::cout << "1 " << N << '\n';
        return 0;
	}
    arr[0] = 0;
	add(0);
	for (int i = 1; i <= N; i++) {
        std::cin >> arr[i];
        arr[i] ^= arr[i-1];
        upd(i);
	}
	std::cout << ans.first+1 << " " << ans.second << '\n';
	return 0;
}

• Subtask 1: 100 / 100