Cod sursa(job #87866)

Utilizator recviemAlexandru Pana recviem Data 29 septembrie 2007 14:20:46
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
using namespace std;
struct deque
{
    int pos,val;
} q[500000];
    int v[500000];
    int n,k;
    int d1,d2;
    int last,first,baza;

void citire()
{
    freopen("secventa.in","r",stdin);
    scanf("%d%d",&n,&k);
    for (int i=0;i<n;i++)
        scanf("%d",&v[i]);
    fclose(stdin);
}

void calcul()
{

    d1=0;
    d2=0;
    q[0].val=v[0];
    q[0].pos=0;
    for (int i=1;i<n;i++)
    {
        while (q[d1].pos<=i-k && d1<=d2)
            d1++;
        while (q[d2].val>=v[i] && d2>=d1)
            d2--;
        d2++;
        q[d2].val=v[i];
        q[d2].pos=i;
        if (((q[d1].val > baza) && (i>k-1)) || (i==k-1))
        {
            baza=q[d1].val;
            first=i-k+2;
            last=i+1;
        }

    }
}

int main()
{
    citire();
    calcul();
    freopen("secventa.out","w",stdout);
    printf("%d %d %d",first,last,baza);
    fclose(stdout);
    return 0;
}