Cod sursa(job #2936970)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 9 noiembrie 2022 18:28:07
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda cnilc1_2-dq Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f( "secventa.in" );
ofstream g( "secventa.out" );

int A[500010],N, k;

deque<int> DQ;


int main()
{
    f >> N >> k;
    for( int i = 1; i <= k; i++ ) {
        f >> A[ i ];
        while( !DQ.empty() && A[ DQ.back() ] > A[ i ] )
            DQ.pop_back();
        DQ.push_back( i );
    }

    int Max = A[ DQ.front() ];
    int final = k;

    for( int i = k + 1; i <= N; i++ ) {
        f >> A[ i ];
        if( DQ.front() <= i - k ) DQ.pop_front();

        while( !DQ.empty() && A[ DQ.back() ] > A[ i ] ) DQ.pop_back();

        DQ.push_back( i );

        if( Max < A[ DQ.front() ] ) {
            Max = A[ DQ.front() ];
            final = i;
        }
    }

    g << final - k + 1 << ' ' << final << ' ' << Max << '\n';
    return 0;
}