Submission #378510

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
378510	2021-03-17T01:10:54 Z	ijxjdjd	XOR (IZhO12_xor)	C++14	100 / 100	217 ms	91500 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	88428 KB	Output is correct
2	Correct	55 ms	88428 KB	Output is correct
3	Correct	57 ms	88444 KB	Output is correct
4	Correct	57 ms	88684 KB	Output is correct
5	Correct	62 ms	88556 KB	Output is correct
6	Correct	64 ms	88556 KB	Output is correct
7	Correct	66 ms	88556 KB	Output is correct
8	Correct	66 ms	88576 KB	Output is correct
9	Correct	105 ms	88812 KB	Output is correct
10	Correct	103 ms	88812 KB	Output is correct
11	Correct	103 ms	88812 KB	Output is correct
12	Correct	112 ms	88812 KB	Output is correct
13	Correct	111 ms	88916 KB	Output is correct
14	Correct	109 ms	88812 KB	Output is correct
15	Correct	106 ms	88812 KB	Output is correct
16	Correct	105 ms	88812 KB	Output is correct
17	Correct	208 ms	89324 KB	Output is correct
18	Correct	208 ms	91372 KB	Output is correct
19	Correct	217 ms	91500 KB	Output is correct
20	Correct	216 ms	91372 KB	Output is correct