Cod sursa(job #2472352)

Utilizator SoranaAureliaCatrina Sorana SoranaAurelia Data 12 octombrie 2019 11:45:43
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <algorithm>
using namespace std;

const int MAXN = 500041;
int d[MAXN];
int a[MAXN], n, k;
int st, dr;

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


void citire(){
    f>>n>>k;
    for(int i=0; i<n; i++)
        f>>a[i];
}

void addElement(int pos){
    while(dr>st && a[d[dr-1]] >= a[pos])
        dr--;
    d[dr] = pos;
    dr++;
}

int pickElement(int pos){

    while(pos - d[st] >= k) ///prea vechi
        st++;
    return d[st];
}

int istart, ifin;
void solve(){

    for(int i=0; i<k-1; i++){
        addElement(i);
    }
    int vmax = -30000;
    for(int i=k-1; i<n; i++){
        addElement(i);
        int baza = a[pickElement(i)];
        if(baza > vmax){
            vmax = baza;
            istart = i - k + 1;
            ifin = i;
        }

    }
    g<<istart+1<<" "<<ifin+1<<" "<<vmax;
}
int main()
{
    citire();
    solve();
    return 0;
}