Submission #503342

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
503342	2022-01-07T16:51:15 Z	LucaIlie	XOR (IZhO12_xor)	C++17	100 / 100	992 ms	217664 KB

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] = min( 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 );

        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] );
                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] );
        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.0 / 100.0

#	Verdict	Execution time	Memory	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	3 ms	1356 KB	Output is correct
5	Correct	28 ms	9268 KB	Output is correct
6	Correct	48 ms	13392 KB	Output is correct
7	Correct	39 ms	12724 KB	Output is correct
8	Correct	39 ms	13928 KB	Output is correct
9	Correct	306 ms	69636 KB	Output is correct
10	Correct	346 ms	69744 KB	Output is correct
11	Correct	274 ms	65728 KB	Output is correct
12	Correct	265 ms	65716 KB	Output is correct
13	Correct	252 ms	61816 KB	Output is correct
14	Correct	283 ms	65792 KB	Output is correct
15	Correct	438 ms	93964 KB	Output is correct
16	Correct	226 ms	61816 KB	Output is correct
17	Correct	911 ms	207876 KB	Output is correct
18	Correct	791 ms	165332 KB	Output is correct
19	Correct	992 ms	217664 KB	Output is correct
20	Correct	810 ms	155540 KB	Output is correct