Cod sursa(job #1279598)

Utilizator danysilas23Silas Daniel danysilas23 Data 30 noiembrie 2014 17:00:52
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 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;
}