Cod sursa(job #1025066)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 9 noiembrie 2013 14:36:16
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include<cstring>
using namespace std;
ofstream fout ("secventa.out");
ifstream fin ("secventa.in");
//FILE *fin = fopen("secventa.in","r");
//FILE *fout = fopen("secventa.out","w");

int n,k,front,back,i,d[500010];
int v[500010],maxim,inceput,semn,x;
char s[4000001],c;

int main () {

    fin>>n>>k;
    fin.get();
    fin.get (s,4000000);
    n=0;semn=1;
    for(i=0;s[i]!=0;i++){
        if (s[i]=='-')
            semn=-1;
        else
            if(s[i]>='0'&&s[i]<='9')
                x=x*10+s[i]-'0';
            else {
                v[++n]=x*semn;
                x=0;
                semn=1;
        }
    }
    v[++n]=x;
    front = 1; back = 0; maxim=-30010;

    for (i=1;i<=n;i++) {

        while (front<=back && v[i] <= v[d[back]]) back --;

        d[++back]= i;

        if (i - d[front] == k)
            front ++;

        if (i>=k)
            if (v[d[front]] > maxim) {
                maxim=v[d[front]];
                inceput=i;
            }
    }
    //fprintf(fout,"%d ",inceput-k+1);
    //fprintf(fout,"%d ",inceput);
    //fprintf(fout,"%d\n",maxim);

    fout << inceput-k+1 << " " << inceput << " " << maxim << "\n";

    return 0;
}