Cod sursa(job #1514316)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 30 octombrie 2015 23:44:11
Problema Secventa Scor 30
Compilator c Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#include <stdlib.h>
struct gogu
{
    int val;
    int pos;
}v[500001];
int main()
{
    int n,k,s,max,a,b,i,x,pas,j;
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d",&n,&k);
    s=0;
    max=-1000000000;
    a=0;
    b=0;
    v[0].val=max;
    for(i=1; i<=n; i++)
    {
        scanf("%d",&x);
        while(s>0 && x<v[s].val)
            s--;
        if(x>v[s].val){
            v[++s].val=x;
            v[s].pos=i;
        }
        if(i>=k)
        {
            pas=1<<20;
            j=0;
            while(pas>0)
            {
                if(j+pas<=s && v[j+pas].pos<=i-k+1)
                    j+=pas;
                pas>>=1;
            }
            if(v[j+pas].pos<i-k+1)
                j++;
            if(v[j].val>max)
            {
                max=v[j].val;
                a=v[j-1].pos+1;
                b=i;
            }
            else
                if(v[j].val==max)
                    if(v[j-1].pos+1<a)
                    {
                        a=v[j-1].pos+1;
                        b=i;
                    }
        }
    }
    printf("%d %d %d\n",a,b,max);

    return 0;
}