Submission #503339

#	Time	Username	Problem	Language	Result	Execution time	Memory
503339		LucaIlie	XOR (IZhO12_xor)	C++17	100 / 100	590 ms	219748 KiB

xor

#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 = 0;
        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 );
        ind.aint[norm.ans_xor_part[i - 1]] = min( ind.aint[norm.ans_xor_part[i - 1]], i - 1 );

        for ( p = MAX_LOG_A; p >= 0; p-- ) {
            if ( (x & (1 << p)) == 0 ) {
                //j = ind.query( 0, 0, norm.maxVal, norm.ans_temp[i][p][0], norm.ans_temp[i][p][1] );
                for ( int k = norm.ans_temp[i][p][0]; k <= norm.ans_temp[i][p][1]; k++ ) {
                    j = ind.aint[k];
                    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] );
        j = ind.aint[norm.ans_xor_x[i]];
        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;
}

• Subtask 1: 100 / 100