Cod sursa(job #88076)

Utilizator recviemAlexandru Pana recviem Data 30 septembrie 2007 10:44:02
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 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);
*/
    char sir[400000];
    fgets(sir,10,stdin);
    int i;
    for(i=0; sir[i] != ' '; i++)
        n=n*10 + sir[i]-'0';
    i++;
    for (;sir[i] !='\n';i++)
        k=k*10 + sir[i]-'0';
    // Gata n si k
    fgets(sir,350000,stdin);
    int j=0;
    for (int i=0;i<n;i++)
    {
        if (sir[j]=='-')
        {
            v[i]=-1 * (sir[j+1] -'0');
            j+=2;
        }
        else
            v[i]=0;
        while (('0'<=sir[j]) && (sir[j]<='9'))
        {
            v[i]=v[i]*10 + sir[j]-'0';
            j++;
        }
        j++;
    }
}

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