Cod sursa(job #2514342)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 25 decembrie 2019 15:01:13
Problema Secventa Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 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;
        }
    }
}

void citire(){
    char c;
    int nr=0, semn =1;
    f.get(c);
    while(f.get(c) && c!='\n'){
        if(c<='9' && c>='0')
            a[nr]=a[nr]*10+c-'0';
        else if(c=='-')
            semn=-1;
        else{
            a[nr]=a[nr]*semn;
            semn=1;
            nr++;
        }
    }
}
int main()
{
    f>>n>>k;
    citire();
    adaugPrimaSecventa();
    vmax = a[D.front()];
    start = 0;
    finish = k-1;
    secventaNoua();
    g<<start+1<<" "<<finish+1<<" "<<vmax;
    return 0;
}