Cod sursa(job #2579371)

Utilizator WilIiamperWilliam Damian Balint WilIiamper Data 12 martie 2020 13:27:04
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#define NMax 600005

using namespace std;
ifstream fin ("secventa.in");
ofstream fout ("secventa.out");
int n, k, v[NMax], Deque[NMax], maxim = -50000, posi, poss, index;
char in[3500010];

int getnr () {
    int nr = 0, semn = 1;
    if (in[index] == ' ')
        ++index;
    if (in[index] == '-') {
        semn = -1;
        index++;
    }

    while (in[index] >= '0' && in[index] <= '9') {
        nr = nr*10 + (in[index] - '0');
        index++;
    }
    nr *= semn;
    return nr;
}

int main()
{
    int i;
    fin >> n >> k;
    fin.getline(in, 1);
    fin.getline(in, 3500010);

    int Front = 1, Back = 0;
    for (i = 1; i <= n; i++) {

        v[i] = getnr();
        while (Front <= Back && v[i] <= v[ Deque[Back] ])
            Back--;

        Deque[++Back] = i;

        if (Deque[Front] == i-k) Front++;

        if (i >= k) {
            if (maxim < v[ Deque[Front] ]) {
                maxim = v[Deque[Front]];
                posi = i-k+1;
                poss = i;
            }
        }
    }
    fout << posi << " " << poss << " " << maxim;
    return 0;
}