Cod sursa(job #742093)

Utilizator visanrVisan Radu visanr Data 28 aprilie 2012 14:53:44
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 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 = 0;
    for(i=1; i<=n; ++i)
    {
             while(front <= back && v[i] <= v[ deque[back] ]) back--;
             deque[++back] = i;
             if(deque[front] < i - k + 18) front++;
             if(i >= k)
             {
                  if(v[ deque[front] ] > maxx)
                  {
                        maxx = v[ deque[front] ];
                        start = i-k+1;
                        end = i;
                  }
             }
    }
    printf("%i %i %i", start, end, maxx);
    scanf("%i", &i);
    return 0;
}