Cod sursa(job #1491226)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 24 septembrie 2015 22:52:04
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.36 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];
    int m;
    /*for(m=st;m<u;m++)
        printf("%d ", v[s[m]]);
    printf("\n");*/
    for(i=k;i<n;i++){
        if(s[st]==i-k)
            st++;
        int a=st, b=u;
        if(v[i]>v[s[u-1]])
            s[u++]=i;
        else{
            while(b-a>1){
                m=(a+b)/2;
                if(v[s[m]]<v[i])
                    a=m+1;
                else
                    b=m;
            }
            if(v[i]<=v[a]){
                s[a]=i;
                u=a+1;
            }
            else{
                s[b]=i;
                u=b+1;
            }
        }
        if(v[s[st]]>v[max]){
            max=s[st];
            p=i-k+1;
        }
        /*printf("%d %d %d     ", st, u, a);
        for(m=st;m<u;m++)
            printf("%d ", v[s[m]]);
        printf("\n");*/
    }
    fprintf(fo,"%d %d %d", p+1, p+k, v[max]);
    fclose(fi);
    fclose(fo);
    return 0;
}