Submission #1248508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248508		xydwe12312	XOR (IZhO12_xor)	C++20	100 / 100	150 ms	86592 KiB

xor

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long

const int mod = 1000000007; // 998244353;
const int N = 2e5 + 5;

struct Node {

	Node *links[2];
	int prefix;
	int min_value = 1e9;

	Node *getKey(int bit) {
		return links[bit];
	}

	bool containsKey(int bit) {
		return (links[bit] != NULL);
	}

	void createTrie(int bit, Node *node) {
		links[bit] = node;
	}

	void inc(Node *node) {
		node->prefix++;
	}

	void dec(Node *node) {
		node->prefix--;
	}
};

class Trie {

private:
	Node *root;

public:
	vector<int> bits;
	Trie() {
		root = new Node();
		bits = vector<int>(31, 0);
	}

	void add(vector<int> &bits, int i, Node* &node, int idx) {

		if (i < 0) {
			node -> min_value = min(node -> min_value, idx);
			return;
		}

		int bit = bits[i];

		if (!node->containsKey(bit)) node->createTrie(bit, new Node());

		Node* next = node->getKey(bit);
		add(bits, i - 1, next, idx);

		node -> min_value = min(node -> min_value, next -> min_value);

	}

	void insert(int n, int idx) {

		Node *node = root;

		int x = n;
		for (int i = 0; i < 31; i++) {
			bits[i] = (x & 1);
			x >>= 1;
		}

		add(bits, 30, node, idx);
	}

	int query(int x, int k)
	{

		Node *node = root;
		int _x = x;

		for (int i = 0; i < 31; i++)
		{
			bits[i] = (_x & 1);
			_x >>= 1;
		}

		int ans = 1e9, sum = 0;

		for (int i = 30; i >= 0; i--)
		{
			int bit = bits[i];
			if ((sum | (1 << i)) > k)
			{
				if (node->containsKey(1 - bit))
					ans = min(ans, node->getKey(1 - bit) -> min_value);
				if (node->containsKey(bit)) node = node->getKey(bit);
				else break;
			}
			else
			{
				sum |= (1 << i);
				if (node->containsKey(1 - bit)) node = node->getKey(1 - bit);
				else break;
			}
		}

		return ans;
	}
};

void solve() {

	int n, x; cin >> n >> x;

	vector<int> a(n);
	for (auto &i : a) cin >> i;


	for (int i = 1; i < n; i++) a[i] ^= a[i - 1];

	int idx = 1, len = 0;
	for (int i = 0; i < n; i++) {
		if (a[i] >= x) {
			len = i + 1;
		}
	}

	Trie trie;
	trie.insert(a[0], 0);

	for (int i = 1; i < n; i++) {
		int min_idx = trie.query(a[i], x - 1);
		if (i - min_idx > len) {
			len = i - min_idx;
			idx = i - len + 2;
		}
		trie.insert(a[i], i);
	}

	cout << idx << " " << len << "\n";
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1; while (t--) solve();
	return 0;
}

• Subtask 1: 100 / 100