Cod sursa(job #91842)

Utilizator recviemAlexandru Pana recviem Data 13 octombrie 2007 15:58:32
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#include <string>
using namespace std;
struct deque
{
    int pos,val;
} q[500000];

    int v[500000];
    long n=0,k=0,l;
    int d1,d2;
    int last,first,baza;
    char c,input[3500000];

void citire()
{
    long i=0,j=0;
    char delims[] = " ";
    char *result = NULL;

    freopen("secventa.in","r",stdin);
    scanf("%ld%ld",&n,&k);
    getc(stdin);
    fgets(input,3500000,stdin);
    result = strtok( input, " " );
    while( result != NULL )
    {
        v[i++] = atoi(result) ;
        result = strtok( NULL, " " );
    }
}

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