Cod sursa(job #1278817)

Utilizator felixiPuscasu Felix felixi Data 29 noiembrie 2014 14:35:40
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 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;
int v[NMAX+1];

string s;
string::iterator it;

int Next_i32() {
    int semn = 1, sol = 0;
    while ( ( *it < '0' || *it > '9' ) && *it != '-' ) {
        ++ it;
    }
    if ( *it == '-' ) {
        semn = -1; ++ it;
    }
    while( it != s.end() && *it >= '0' && *it <= '9' ) {
        sol = sol * 10 + *it - '0';
        ++ it;
    }
    return sol * semn;
}

int main() {
    getline( in, s, (char)0 );
    it= s.begin();
    N= Next_i32();  K= Next_i32();
    for( int i= 1;  i<=K;  ++i ) {
        v[i]= Next_i32();
        while( !dq.empty() && v[i] < v[ dq.back() ] )
            dq.pop_back();
        dq.push_back( i );
    }
    Mx= v[ dq.front() ];  st= 1;
    for( int i= K+1;  i<=N;  ++i ) {
        v[i]= Next_i32();
        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;
        }
    }
    out << st << ' ' << st+K-1 << ' ' << Mx << '\n';
    return 0;
}