Cod sursa(job #742094)

Utilizator visanrVisan Radu visanr Data 28 aprilie 2012 14:57:06
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;


#define nmax 500010


int v[nmax], deque[nmax], n, k, maxx = -nmax, start, end, front, back;
char s[50000], *p, sep[]=" ";

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int i=1,j;
    scanf("%i %i", &n, &k);/*
    p = strtok(s, sep);
    while(p != NULL)
    {
                  int sum = 0;
                  if(p[0]=='-')
                  {
                               for(j = 1; j < strlen(p); ++j) sum = sum*10 + (p[j] - '0');
                               sum *= (-1);
                  }else
                  {
                       for(j = 0; j < strlen(p); ++j) sum = sum*10 + (p[j] - '0');
                  }
                  v[i++] = sum;
                  p = strtok(NULL, sep);
    }             */
    for(i=1; i<=n; ++i) scanf("%i", &v[i]);
    front = 1;
    back = 1;
    deque[1] = 1;
    for(i = 2; i < k; ++i)
    {
             while(front <= back && v[i] <= v[ deque[back] ]) back--;
             deque[++back] = i;
    }
    for(i = k; i<=n; ++i)
    {
             while(front <= back && v[i] <= v[ deque[back] ]) back--;
             deque[++back] = i;
             if(v[ deque[front] ] > maxx)
             {
                        maxx = v[ deque[front] ];
                        start = i - k + 1;
                        end = i;
             }
             if(deque[front] < i - k + 2) front++;
    }
    printf("%i %i %i", start, end, maxx);
    scanf("%i", &i);
    return 0;
}