Cod sursa(job #1793662)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 31 octombrie 2016 12:37:37
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

int n, i, j, a[500005];
int fr, bk, dq[500005];
int maxim = -5e+4, ml, mr, k;
char s[3100000];

void citire() {
    int w = 0, semn, nr = 0;
    f.getline(s, 3099999);
    int l = strlen(s);
    for (i = 0; i < l;) {
        semn = 1, nr = 0;
        if (s[i] == '-') semn=-1, i++;
        while (s[i] >= '0' && s[i] <= '9')
            nr = nr*10 + s[i] - '0', i++;
        while (s[i] == ' ') i++;
        a[++w] = nr*semn;
    }
}

int main() {
    f >> n >> k; f.get();
    citire();

    fr = 1, bk = 0;
    for (i = 1; i <= n; i++) {
        while (fr <= bk && a[dq[bk]] >= a[i])
            bk--;

        dq[++bk] = i;

        if (dq[bk] - dq[fr] == k)
            fr++;

        if (a[dq[fr]] > maxim && dq[bk] >= k)  {
            maxim = a[dq[fr]];
            ml = dq[bk]-k+1;
            mr = dq[bk];
        }
    }
    g << ml << ' ' << mr << ' ' << maxim;
    return 0;
}