Cod sursa(job #1493619)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 29 septembrie 2015 18:32:36
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#include <stdlib.h>

int v[500000], s[500000];
char cf[256];

void init(){
    int i;
    for(i='0';i<='9';i++)
       cf[i]=1;
}

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);
    fgetc(fi);
    char c;
    int acc=0, semn=1;
    c=fgetc(fi);
    i=0;
    init();
    while(c!='\n' && c!=EOF){
        if(c=='-')
            semn=-1;
        else if(cf[c]==1){
            acc*=10;
            acc+=c-'0';
        }
        else{
            v[i++]=semn*acc;
            acc=0;
            semn=1;
        }
        c=fgetc(fi);
    }
    v[i]=semn*acc;

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