Submission #338632

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
338632	2020-12-23T14:19:06 Z	amunduzbaev	XOR (IZhO12_xor)	C++14	100 / 100	144 ms	22380 KB

xor

/** made by amunduzbaev **/
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long 
#define ld long double 
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)

const int N = 250005 ;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

int n, m, k, ans, a[N];
int tree[N*30][2], node, sub[N*30];

void sett(int x, int ind){
	int now = 0;
	for(int i=29;i>=0;i--){
		int bit = (x>>i)&1;
		if(tree[now][bit]) now = tree[now][bit];
		else{
			tree[now][bit] = ++node;
			now = node;
			sub[now] = n+1;
		}
		sub[now] = min(sub[now], ind);
	}
}
 
int get(int i, int x, int now, int cur){
	if(cur >= k) return sub[now];
	if(i<0 || cur + (1<<(i+1))-1 < k) return n+1;
	
	int bit = (x>>i)&1, res = n+1;
	for(int j=0;j<2;j++)
		if(tree[now][j]) res = min(res, get(i-1, x, tree[now][j], (cur + (j != bit ? (1<<i) : 0))));
	return res;
}
 
void solve(){
	fastios 
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i] ^= a[i-1];
	}
	int l = 1, r = 1;
	for(int i=1;i<=n;i++){
		sett(a[i-1], i);
		int lx = get(29, a[i], 0, 0);
		if(i - lx > r - l) r = i, l = lx;
	}
	cout<<l<<" "<<r-l+1<<endl;
	return;
}
 
 
int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct
5	Correct	6 ms	1004 KB	Output is correct
6	Correct	8 ms	1004 KB	Output is correct
7	Correct	8 ms	1004 KB	Output is correct
8	Correct	9 ms	1132 KB	Output is correct
9	Correct	43 ms	10732 KB	Output is correct
10	Correct	46 ms	10732 KB	Output is correct
11	Correct	45 ms	10644 KB	Output is correct
12	Correct	42 ms	10732 KB	Output is correct
13	Correct	43 ms	10696 KB	Output is correct
14	Correct	57 ms	10732 KB	Output is correct
15	Correct	47 ms	10860 KB	Output is correct
16	Correct	44 ms	10732 KB	Output is correct
17	Correct	144 ms	22380 KB	Output is correct
18	Correct	129 ms	22380 KB	Output is correct
19	Correct	131 ms	22380 KB	Output is correct
20	Correct	138 ms	22380 KB	Output is correct