Cod sursa(job #2485064)

Utilizator FlaviusFeteanFetean Flavius FlaviusFetean Data 31 octombrie 2019 22:22:07
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <cstring>

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

int dq[500005], v[500005];
char s[31000000];

int main()
{
    int N, K, L, i, x = 0, b = 1, e = 0, bSirCerut, minimax;
    int P, j = 0, sgn = 1;

    fin >> N >> K;
    fin.get(s[0]);
    fin.getline(s, 31000000);

    L = strlen(s); P = 1;

    for(i = 0; i < L; i++){
        if(s[i] != ' '){
            if(s[i] != '-'){
                x += P*(s[i]-48);
                P *= 10;
            }
            else  sgn = -1;
        }
        else{
            v[++j] = x * sgn;
            sgn = 1;
            x = 0; P = 1;
        }
    }

    v[N] = x * sgn;

    for(i = 1; i <= K; i++){
        dq[++e] = v[i];
        while(e > b && dq[e] < dq[e - 1]) dq[--e] = dq[e + 1];
    }
    minimax = dq[1]; bSirCerut = 1;
    for(i = K + 1; i <= N; i++){
        if(dq[b] == v[i - K]) b++;
        dq[++e] = v[i];
        while(e > b && dq[e] < dq[e - 1]) dq[--e] = dq[e + 1];
        if(dq[b] > minimax) minimax = dq[b], bSirCerut = i - K + 1;
    }

    fout << bSirCerut << ' ' << bSirCerut + K - 1 << ' ' << minimax;

    return 0;
}