Cod sursa(job #2784708)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 17 octombrie 2021 02:22:38
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>


using namespace std;

const int N = 500001;
int v[ N ], q[ N ], p[ N ];

int main( ) {
    
    ifstream fin ( "secvente.in" );
    ofstream fout ( "secvente.out" );
    
    int n, k, i, st, dr, e, poz;
    
    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 ];
    poz = 0;

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