Cod sursa(job #1755016)

Utilizator Dan_RadulescuRadulescu Dan Dan_Radulescu Data 9 septembrie 2016 10:54:53
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<fstream>
using namespace std;
ifstream fin("secventa.in");
ofstream fout("secventa.out");
char buff[3000100];
int n,k,i,maxs=-30001,p,u,coada[600001],v[600001],st,fi,poz=0,m;
void read(int &numar){
    char semn='+';
    numar=0;
    if (buff[poz]=='-') {
            semn='-';
            poz++;
    }
    while(buff[poz]>='0' && buff[poz]<='9'){
        numar=numar*10+buff[poz]-'0';
        poz++;
    }
    poz++;
    if (semn=='-') numar=-numar;
}
int main(){
    fin.getline(buff,3000100);
    read(n);
    read(k);
    poz=0;
    fin.getline(buff,3000100);
    for (i=1;i<=n;i++){
        read(m);
        v[i]=m;
    }
    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]]){
           if (i-coada[p]<k-1){
              st=i-k+1;
              fi=i;
              maxs=v[coada[p]];
           }
            else{
              st=coada[p];
              fi=i;
              maxs=v[coada[p]];
            }
        }
    }
    fout<<st<<" "<<fi<<" "<<maxs;
    fout.close();
    return 0;
}