UVA 1608 Non-boring sequences ( DC )

UVa Online Judge
It is obvious that once we find an element that is "non-boring", we can split segment to two sub segments to apply divide and conquer for each. The problem is that if we try to find that "non-boring" element from either side, there is a risk that it would always search until the other end, thus holds O( n ^ 2 ) worst time complexity. An easy work around would be to search from each end towards the middle. This way the worst case will be when the element is in the middle. However it is T( n ) = 2T( n / 2 ) + O( n ), which, similar to quick sort, is O( n lg n ).

/* 
 * memset -> TLE > 3.000 s
 * map.clear() -> AC = 0.755 s
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2 * 1e5 + 5;

int seq[MAXN];
// int lft[MAXN], rit[MAXN];
map<int, int> lft, rit;

void buildLftRit(int n){
    // memset( lft, -1, sizeof(lft) );
    // memset( rit, -1, sizeof(rit) );
    lft.clear(); rit.clear();
    map<int, int> lst;
    for(int i = 0; i < n; ++i){
        if( lst.count( seq[i] ) ) lft[i] = lst[ seq[i] ];
        lst[ seq[i] ] = i;
    }
    lst.clear();
    for(int i = n - 1; i >= 0; --i){
        if( lst.count( seq[i] ) ) rit[i] = lst[ seq[i] ];
        lst[ seq[i] ] = i;
    }
}

bool isUnique(int k, int l, int r){
    if( lft.count(k) && lft[k] >= l ) return false;
    if( rit.count(k) && rit[k] < r ) return false;
    return true;
}

bool notBoring(int l, int r){ // [l, r)
    if( l + 1 >= r ) return true;
    if( l + 2 == r ) return seq[l] != seq[l + 1];
    for(int i = l, j = r - 1; i <= j; ++i, --j){
        if( isUnique( i, l, r ) )
            return notBoring( l, i ) && notBoring( i + 1, r );
        if( isUnique( j, l, r ) )
            return notBoring( l, j ) && notBoring( j + 1, r );
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while( T-- ){
        int n; cin >> n;
        for(int i = 0; i < n; ++i)
            cin >> seq[i];
        buildLftRit( n );

        if( notBoring(0, n) ) cout << "non-boring" << endl;
        else cout << "boring" << endl;
    }
    return 0;
}