#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 250000
#define MAX_NORM 16000000
#define MAX_LOG_A 30
int xor_part[MAX_N + 1];
struct normalizare {
struct pozitie {
int tip, i1, i2, i3;
};
struct element {
int val;
pozitie poz;
bool operator < (const element &a) const {
return val < a.val;
}
};
int size, maxVal;
element v[MAX_NORM + 1];
int ans_xor_part[MAX_N + 1];
int ans_temp[MAX_N + 1][MAX_LOG_A + 1][2];
int ans_xor_x[MAX_N + 1];
void add( element a ) {
v[size] = a;
size++;
}
void normalizeaza() {
int i;
sort( v, v + size );
maxVal = 1;
for ( i = 0; i < size; i++ ) {
if ( v[i].poz.tip == 1 )
ans_xor_part[v[i].poz.i1] = maxVal;
else if ( v[i].poz.tip == 2 )
ans_temp[v[i].poz.i1][v[i].poz.i2][v[i].poz.i3] = maxVal;
else
ans_xor_x[v[i].poz.i1] = maxVal;
if ( i < size - 1 && v[i].val != v[i + 1].val )
maxVal++;
}
}
};
struct AINT {
vector <int> aint;
void init( int size ) {
int i;
for ( i = 0; i < 4 * size; i++ )
aint.push_back( MAX_N + 1 );
}
int query( int nod, int l, int r, int lq, int rq ) {
int mid;
mid = (l + r) / 2;
if ( l > rq || r < lq )
return MAX_N + 1;
if ( lq <= l && r <= rq )
return aint[nod];
return min( query( nod * 2 + 1, l, mid, lq, rq ), query( nod * 2 + 2, mid + 1, r, lq, rq ) );
}
void update( int nod, int l, int r, int p, int x ) {
int mid;
mid = (l + r) / 2;
if ( l > p || r < p )
return;
if ( l == r ) {
aint[nod] = x;
return;
}
update( nod * 2 + 1, l, mid, p, x );
update( nod * 2 + 2, mid + 1, r, p, x );
aint[nod] = min( aint[nod * 2 + 1], aint[nod * 2 + 2] );
}
};
normalizare norm;
AINT ind;
int main() {
int n, a, x, y, temp, maxLen, poz, p, i, j;
cin >> n >> x;
for ( i = 1; i <= n; i++ ) {
cin >> a;
xor_part[i] = xor_part[i - 1] ^ a;
}
for ( i = 0; i <= n; i++ )
norm.add( { xor_part[i], { 1, i, 0, 0 } } );
for ( i = 1; i <= n; i++ ) {
y = 0;
for ( p = MAX_LOG_A; p >= 0; p-- ) {
if ( x & (1 << p) ) {
if ( (xor_part[i] & (1 << p)) == 0 )
y += (1 << p);
} else {
temp = y;
if ( xor_part[i] & (1 << p) )
y += (1 << p);
else
temp += (1 << p);
norm.add( { temp, { 2, i, p, 0 } } );
norm.add( { temp + (1 << p) - 1, { 2, i, p, 1 } } );
}
}
norm.add( { x ^ xor_part[i], { 3, i, 0, 0 } } );
}
norm.normalizeaza();
ind.init( norm.maxVal );
maxLen = 0;
poz = -1;
for ( i = 1; i <= n; i++ ) {
ind.update( 0, 0, norm.maxVal, norm.ans_xor_part[i - 1], i - 1 );
y = 0;
for ( p = MAX_LOG_A; p >= 0; p-- ) {
if ( x & (1 << p) ) {
if ( (xor_part[i] & (1 << p)) == 0 )
y += (1 << p);
} else {
if ( xor_part[i] & (1 << p) )
y += (1 << p);
j = ind.query( 0, 0, norm.maxVal, norm.ans_temp[i][p][0], norm.ans_temp[i][p][1] );
for ( j = 0; j < i; j++ ) {
if ( norm.ans_temp[i][p][0] <= norm.ans_xor_part[j] && norm.ans_xor_part[j] <= norm.ans_temp[i][p][1] ) {
if ( i - j > maxLen ) {
maxLen = i - j;
poz = j + 1;
} else if ( i - j == maxLen ) {
if ( j + 1 < poz )
poz = j + 1;
}
}
}
}
}
j = ind.query( 0, 0, norm.maxVal, norm.ans_xor_x[i], norm.ans_xor_x[i] );
for ( j = 0; j < i; j++ ) {
if ( norm.ans_xor_x[i] == norm.ans_xor_part[j] ) {
if ( i - j > maxLen ) {
maxLen = i - j;
poz = j + 1;
} else if ( i - j == maxLen ) {
if ( j + 1 < poz )
poz = j + 1;
}
}
}
}
cout << poz << " " << maxLen;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1356 KB |
Output is correct |
| 5 |
Correct |
460 ms |
9288 KB |
Output is correct |
| 6 |
Correct |
1058 ms |
13400 KB |
Output is correct |
| 7 |
Correct |
810 ms |
12644 KB |
Output is correct |
| 8 |
Correct |
1088 ms |
13892 KB |
Output is correct |
| 9 |
Execution timed out |
2078 ms |
69652 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
