Cod sursa(job #2784682)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 17 octombrie 2021 00:20:12
Problema Secventa Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>

using namespace std;

const int N = 100000;
int v[ N ], q[ N ];

int main( ) {
    
    ifstream fin ( "secventa.in" );
    ofstream fout ( "secventa.out" );
    
    int n, k, i, st, dr, e;
    
    fin >> n >> k;
    
    for ( i = 0; i < n; i++ )
        fin >> v[ i ];
    
    st = 0;
    dr = 0;
    q[ 0 ] = v[ 0 ];
    
    for ( i = 1; i < k; i++ ){
        
        while( q[ dr ] > v[ i ] && dr >= 0 )
            dr--;
        dr++;
        q[ dr ] = v[ i ];
    }

    e = q[ st ];
    st++;
    
    for ( i = k; i < n; i++ ){
        
        while( q[ dr ] > v[ i ] && dr >= st )
            dr--;
        dr++;
        q[ dr ] = v[ i ];
        
        if ( q[ st ] > e )
            e = q[ st ];
        
        if ( q [ st ] == v[ i - k ] )
            st++;
        
    }
    
    if ( q[ st ] > e )
        e = q[ st ];
    
    i = 0;
    while( v[ i ] != e )
        i++;
    
    st = i;
    dr = i;
    
    while( e <= v[ st ] && st >= 0 )
        st--;
    
    if ( st != i )
        st++;
    
    while( e <= v[ dr ] && dr < n )
        dr++;
    
    if ( dr != i )
        dr--;
    
    fout << st + 1 << " " << dr + 1 << " " << e;
    
    return 0;
}