Cod sursa(job #2033788)

Utilizator k.bruenDan Cojocaru k.bruen Data 7 octombrie 2017 10:42:48
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>

std::ifstream in("secventa.in");
std::ofstream out("secventa.out");

int numere, elemente;
int element[500000];
int indice[500000];
int start = 0, stop = 0;
int startMax = 0, stopMax = 0, Max = 0;

void add(int minLimit, int i) {
    while (indice[start] < minLimit) start++;

    if (start == stop) {
        indice[start] = i;
        stop++;
        return;
    }

    while(start != stop && element[i] <= element[indice[stop - 1]]) stop--;
    indice[stop] = i;
    stop++;
}

int main() {
    std::ios::sync_with_stdio(false);

    in >> numere >> elemente;
    for (int i = 0; i < numere; i++) {
        in >> element[i];
    }

    for (int i = 0; i < elemente - 1; i++) add(0, i);
    for (int i = elemente - 1; i < numere; i++) {
        add(i - elemente + 1, i);
        if (element[indice[start]] > Max) {
            Max = element[indice[start]];
            startMax = indice[start];
            stopMax = indice[start] + elemente - 1;
        }
    }

    out << startMax + 1 << " " << stopMax + 1 << " " << Max;

    return 0;
}