Cod sursa(job #1754984)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 9 septembrie 2016 09:35:42
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<fstream>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
int n,k,i,maxs=-30001,p,u,coada[500001],v[500001],st,fi;
int main(){
    fin>>n>>k;
    for (i=1;i<=n;i++)
        fin>>v[i];
    fin.close();
    p=1;u=0;
    for (i=1;i<=n;i++){
        while(p<=u && v[coada[u]]>v[i]) u--;
        u++;
        coada[u]=i;
        if (i-coada[p]>=k) p++;
        if (i>=k && maxs<v[coada[p]]){
              st=coada[p];
              fi=i;
              maxs=v[coada[p]];
        }
    }
    if (fi-st<k-1) fout<<fi-k+1<<" "<<fi<<" "<<maxs;
     else
       fout<<st<<" "<<fi<<" "<<maxs;
    fout.close();
    return 0;
}