답안 #503339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
503339	2022-01-07T16:48:34 Z	LucaIlie	XOR (IZhO12_xor)	C++17	100 / 100	590 ms	219748 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] = 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.0 / 100.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	3 ms	1356 KB	Output is correct
5	Correct	19 ms	9280 KB	Output is correct
6	Correct	28 ms	13412 KB	Output is correct
7	Correct	23 ms	12648 KB	Output is correct
8	Correct	26 ms	14000 KB	Output is correct
9	Correct	180 ms	69692 KB	Output is correct
10	Correct	196 ms	70412 KB	Output is correct
11	Correct	163 ms	66492 KB	Output is correct
12	Correct	168 ms	66508 KB	Output is correct
13	Correct	152 ms	62588 KB	Output is correct
14	Correct	163 ms	66572 KB	Output is correct
15	Correct	237 ms	94680 KB	Output is correct
16	Correct	146 ms	62552 KB	Output is correct
17	Correct	590 ms	209852 KB	Output is correct
18	Correct	466 ms	167264 KB	Output is correct
19	Correct	558 ms	219748 KB	Output is correct
20	Correct	424 ms	157424 KB	Output is correct