Cod sursa(job #2485073)

Utilizator FlaviusFeteanFetean Flavius FlaviusFetean Data 31 octombrie 2019 22:28:50
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 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 j = 0, sgn = 1;

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

    L = strlen(s);

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

    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;
}