Cod sursa(job #1491230)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 24 septembrie 2015 22:54:20
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <stdlib.h>

int v[500000], s[500000];
int main()
{
    int n, k, i, max, st, u, p;
    FILE*fi,*fo;
    fi=fopen("secventa.in","r");
    fo=fopen("secventa.out","w");
    fscanf(fi,"%d%d", &n, &k);
    for(i=0;i<n;i++)
        fscanf(fi,"%d", &v[i]);

    st=0;
    u=0;
    p=0;
    for(i=0;i<k;i++){
        while(u>st && v[s[u-1]]>=v[i])
            u--;
        s[u++]=i;
    }
    max=s[st];
    for(i=k;i<n;i++){
        if(s[st]==i-k)
            st++;
        while(u>st && v[s[u-1]]>=v[i])
            u--;
        s[u++]=i;
        if(v[s[st]]>v[max]){
            max=s[st];
            p=i-k+1;
        }
    }
    fprintf(fo,"%d %d %d", p+1, p+k, v[max]);
    fclose(fi);
    fclose(fo);
    return 0;
}