Cod sursa(job #1338815)

Utilizator livliviLivia Magureanu livlivi Data 10 februarie 2015 13:17:51
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>
#include<cstdio>
#define MAX 500000
using namespace std;

int v[MAX+1];
int n;

int st[MAX+1];
int ic,sf;

char s[7*MAX];

void cit(){
    int i=0,sgn=1,nr=0;

    gets(s);
    while(s[i]!=NULL){
        if (s[i]==' '){
            v[n]=nr*sgn;
            sgn=1;
            nr=0;
            n++;
        }
        else
        if (s[i]=='-') sgn=-1;
        else nr=nr*10+s[i]-'0';

        i++;
    }
    v[n]=nr*sgn;
}


int main(){
    freopen ("secventa.in","r",stdin);
    freopen ("secventa.out","w",stdout);
    int i,k,max,poz;

    scanf ("%d%d\n",&n,&k);
    n=1;
    cit();
    //for(i=1;i<=n;i++)
        //scanf ("%d",&v[i]);

    sf=0;
    for(i=1;i<=k;i++){
        while(sf>0 &&v[st[sf-1]]>=v[i]) sf--;
        st[sf]=i;
        sf++;
    }

    ic=0;
    max=v[st[ic]];
    poz=k;
    for(;i<=n;i++){
        while(sf>ic &&v[i]<=v[st[sf-1]]) sf--;
        st[sf]=i;
        sf++;

        if (st[ic]==i-k) ic++;

        if (v[st[ic]]>max){
            max=v[st[ic]];
            poz=i;
        }
    }

    printf ("%d %d %d",poz-k+1,poz,max);
    return 0;
}