Cod sursa(job #3154219)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 3 octombrie 2023 19:53:32
Problema Factoriale Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
ifstream cin("and.in");
ofstream cout("and.out");
long long n, v[ 200005 ];
long long rmq [ 200005 ][ 20] ;
int main()
{
    cin >> n ;

    for ( int i = 1; i <= n ; i ++ )
    {
        cin >> v[ i ] ;
    }

    for ( int i = 1 ; i <= n ; i ++ )
    {
        rmq [ i ][ 0 ] = v[ i ] ;
    }

    for (int j = 1; j <= 19 ; j ++ )
    {
        for ( int i = 1; i + ( 1 << j ) - 1 <= n ; i ++ )
        {
            rmq [i ] [ j ] = (rmq [ i ] [ j - 1 ] & rmq [ i + ( 1 << ( j - 1 ) ) ] [ j - 1 ]) ;
        }
    }

    long long maxlen = -1 ;

    for ( int i = 1; i <= n ; i ++ )
    {
        long long st = i ;
        long long dr = n ;

        long long poz = 0  ;
        while ( st <= dr )
        {
            long long mij = ( st + dr) / 2;

            long long len = mij - i + 1;
            long long val = log2( len ) ;

            if ( (rmq [ i ] [ val ] & rmq [ mij - ( 1 << val ) + 1] [ val ]) != 0  )
            {
                poz = mij ;
                st  =mij + 1;
            }
            else
                dr = mij - 1;
        }


        maxlen = max ( maxlen, poz + 1 - i ) ;
    }

    cout << maxlen << '\n';

    return 0;
}