Cod sursa(job #2096505)

Utilizator osiaccrCristian Osiac osiaccr Data 29 decembrie 2017 12:56:55
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#define DEF 500010
#define INF 30010

using namespace std;

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

int v[DEF], s[DEF], n, k, st = 1, dr, Max, sol, j;

char pars[10000010];

int main () {
    fin >> n >> k;

    fin.get ();
    fin.get (pars, 10000005);

    for (int i = 1; i <= n; ++ i) {
        int semn = 1;
        if (pars[j] == ' ')
            ++ j;
        if (pars[j] == '-') {
            semn = -1;
            ++ j;
        }
        while (pars[j] >= '0' && pars[j] <= '9') {
            v[i] = v[i] * 10 + pars[j] - '0';
            ++ j;
        }
        v[i] *= semn;
    }

    v[0] = INF;

    Max = -INF;

    for (int i = 1; i <= n; ++ i) {
        while (st <= dr && v[i] < v[s[dr]]) {
            -- dr;
        }

        s[++ dr] = i;

        if (s[st] < i - k + 1)
            ++ st;

        if (i >= k && v[s[st]] > Max) {
            Max = v[s[st]];
            sol = i;
        }
    }

    fout << sol - k + 1 << " " << sol << " " << Max;

    return 0;
}