Cod sursa(job #1246138)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 20 octombrie 2014 17:39:31
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream>
#include<deque>
#include<string>

using namespace std;

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

const int inf = 1 << 30;
const int nmax = 500000;
int v[ nmax + 1 ];
deque <int> d;

string s;

int read_i32() {
    int sol = 0;
    string :: iterator it;
    fin >> s;
    it = s.begin();
    if ( s[ 0 ] == '-' ) {
        ++ it;
    }
    for( ; it != s.end(); ++ it ) {
        sol = sol * 10 + *it - '0';
    }
    if ( s[ 0 ] == '-' ) {
        return -sol;
    }
    return sol;
}

int main() {
    int n, k, sol, x;
    n = read_i32(); k = read_i32();
    sol = -inf;
    for( int i = 0; i < n; ++ i ) {
        v[ i ] = read_i32();
        while ( !d.empty() && v[ d.back() ] > v[ i ] ) {
            d.pop_back();
        }
        d.push_back( i );
        if ( i - d.front() >= k ) {
            d.pop_front();
        }

        if ( i >= k - 1 && v[ d.front() ] > sol ) {
            sol = v[ d.front() ];
            x = i - k + 1;
        }
    }

    fout << x + 1 << ' ' << x + k << ' ' << sol << "\n";

    fin.close();
    fout.close();
    return 0;
}