Pagini recente » Cod sursa (job #3127002) | Cod sursa (job #867084) | Cod sursa (job #150056) | Cod sursa (job #2531849) | Cod sursa (job #2823705)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int maxN = 100'005;
int n, xorp[maxN], ans = -1, st, dr;
struct arbore {
int ind;
bool amin;
}arb[4 * (1 << 20)];
void update(int nod, int poz, int depth)
{
if(depth == -1)
{
arb[nod].ind = poz;
arb[nod].amin = true;
return;
}
if(xorp[poz] & (1 << depth))
update(2 * nod + 1, poz, depth - 1);
else
update(2 * nod, poz, depth - 1);
arb[nod].amin = arb[2 * nod].amin | arb[2 * nod + 1].amin;
}
int query(int nod, int val, int depth)
{
if(depth == -1)
return arb[nod].ind;
if(((val & (1 << depth)) && arb[2 * nod].amin == true) || arb[2 * nod + 1].amin == false)
return query(2 * nod, val, depth - 1);
return query(2 * nod + 1, val, depth - 1);
}
int main()
{
fin >> n;
update(1, 0, 20);
for(int i = 1; i <= n; i++)
{
fin >> xorp[i];
xorp[i] ^= xorp[i - 1];
int maxi = query(1, xorp[i], 20);
if(xorp[i] ^ xorp[maxi] > ans)
{
ans = xorp[i] ^ xorp[maxi];
st = maxi + 1;
dr = i;
}
update(1, i, 20);
}
fout << ans << ' ' << st << ' ' << dr << '\n';
}