Cod sursa(job #1338778)

Utilizator livliviLivia Magureanu livlivi Data 10 februarie 2015 12:51:01
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<cstdio>
#define MAX 500000
using namespace std;

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

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

    scanf ("%d%d",&n,&k);

    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;
}