Cod sursa(job #2514338)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 25 decembrie 2019 14:55:11
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <deque>
#define NMAX 500005
using namespace std;

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

int n, k;
int a[NMAX];
int vmax, start, finish;

deque<int> D;

void add(int i){
    while(!D.empty() && a[D.back()]>a[i])
        D.pop_back();
    D.push_back(i);
}

void elimin(int i){
    if(D.front()==i-k)
        D.pop_front();
}

void adaugPrimaSecventa(){
    for(int i=0; i<k; i++)
        add(i);
}

void secventaNoua(){
    for(int i=k; i<n; i++){
        add(i);
        elimin(i);
        if(a[D.front()]>vmax){
            vmax = a[D.front()];
            start = i - k + 1;
            finish = i;
        }
    }
}
int main()
{
    f>>n>>k;
    for(int i=0; i<n; i++){
        f>>a[i];
    }

    adaugPrimaSecventa();
    vmax = a[D.front()];
    start = 0;
    finish = k-1;
    secventaNoua();
    g<<start+1<<" "<<finish+1<<" "<<vmax;
    return 0;
}