Cod sursa(job #1246276)

Utilizator felixiPuscasu Felix felixi Data 20 octombrie 2014 21:10:23
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <deque>

using namespace std;

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

const int INF  = (1<<30);
const int NMAX = 500000;

deque <int> dq;
int N, K, Mx= -INF, st, fn;
int v[NMAX+1];

int main() {
    in >> N >> K;
    for( int i= 1;  i<=K;  ++i ) {
        in >> v[i];
        while( !dq.empty() && v[i] < v[ dq.back() ] ) {
            dq.pop_back();
        }
        dq.push_back( i );
    }
    Mx= v[ dq.front() ];  st= 1;  fn= K;
    for( int i= K+1;  i<=N;  ++i ) {
        in >> v[i];
        if( dq.front() <= i-K )
            dq.pop_front();
        while( !dq.empty() && v[i] < v[ dq.back() ] ) {
            dq.pop_back();
        }
        dq.push_back( i );
        if( v[ dq.front() ] > Mx ) {
            Mx= v[ dq.front() ];
            st= i-K+1;   fn= i;
        }
    }
    out << st << ' ' << fn << ' ' << Mx << '\n';
    return 0;
}