Cod sursa(job #1874718)

Utilizator robx12lnLinca Robert robx12ln Data 10 februarie 2017 12:54:54
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<fstream>
#include<deque>
#include<cstring>
#define INF 2000000000
#define DIM 5000000
using namespace std;
ifstream fin( "secventa.in" );
ofstream fout( "secventa.out" );
int n, k, v[500005], maxim, st, dr, poz, L, semn;
deque<int> d;
char s[DIM];

int main(){

    fin.getline( s, DIM );
    poz = 0;
    L = strlen(s);
    while( s[poz] >= '0' && s[poz] <= '9' && poz < L ){
        n = n * 10 + ( s[poz] - '0' );
        poz++;
    }
    poz++;
    while( s[poz] >= '0' && s[poz] <= '9' && poz < L ){
        k = k * 10 + ( s[poz] - '0' );
        poz++;
    }

    fin.getline( s, DIM );
    poz = 0;
    L = strlen(s);
    for( int i = 1; i <= n; i++ ){
        semn = 1;
        if( s[poz] == '-' ){
            semn = -1;
            poz++;
        }
        while( s[poz] >= '0' && s[poz] <= '9' && poz < L ){
            v[i] = v[i] * 10 + ( s[poz] - '0' );
            poz++;
        }
        v[i] = v[i] * semn;
        poz++;
    }

    maxim = -INF;
    for( int i = 1; i <= n; i++ ){
        while( !d.empty() && v[d.back()] > v[i]  ){
            d.pop_back();
        }
        d.push_back(i);
        if( d.front() <= i - k ){
            d.pop_front();
        }
        if( i >= k ){
            if( maxim < v[d.front()] ){
                maxim = v[d.front()];
                st = i - k + 1;
                dr = st + k - 1;
            }
        }
    }
    fout << st << " " << dr << " " << maxim;
    return 0;
}