Cod sursa(job #877206)

Utilizator Pintilie_AndreiFII-Pintilie Andrei Pintilie_Andrei Data 12 februarie 2013 17:55:23
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>

using namespace std;
int st[500004],poz[500004];

int main()
{
    int i, ul,pr,k,n,x,maxim=0,p1,p2;
    freopen("secventa.in","r",stdin);
    scanf("%d %d %d", &n, &k, &x);
    st[1]=x;
    poz[1]=1;
    ul=pr=1;
    for(i=2; i<=k; i++)
    {
        scanf("%d",&x);
        while(pr<=ul && st[ul]>x)
        ul--;
        ul++;
        st[ul]=x;
        poz[ul]=i;
    }


    maxim=st[pr]; p1=poz[pr]; p2=poz[ul];
    for(i=k+1; i<=n; i++)
    {
        scanf("%d",&x);
        //printf("%d %d",x,i);
        while(pr<=ul && st[ul]>x)
        ul--;
        ul++;
        st[ul]=x;
        poz[ul]=i;
        while(i-poz[pr]>=k)
        pr++;
        if(maxim<st[pr]){ maxim=st[pr]; p1=poz[pr]; p2=poz[pr]+k;  }
        //for(i=pr; i<=ul; i++) printf("%d %d\n",st[i],poz[i]);
        //printf("\n");
    }
    freopen("secventa.out","w",stdout);
    printf("%d %d %d \n",p1,p2,maxim);
        return 0;
}