Cod sursa(job #742124)

Utilizator visanrVisan Radu visanr Data 28 aprilie 2012 16:45:57
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <cstdlib>
using namespace std;


#define nmax 500010


int v[nmax], deque[nmax], n, k, max = -nmax, start, end, front, back;
char s[8*nmax];

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int i, j = 0;
    bool ok = false;
    scanf("%i %i\n", &n, &k);
    fgets(s,8*nmax,stdin);
    int number = 0;
    for(i = 1; i <= n; ++i)
    {
          ok = false;
          while(s[j] == ' ') j++;
          if(s[j] == '-') 
          {
                  j++;
                  ok = true;
          }
          number = 0;
          while(s[j] >='0' && s[j] <='9')
          {
                     number = number * 10 + (s[j] - '0');
                     j++;
          }
          if(ok) v[i] = number * (-1);
          else v[i] = number;
    }        
    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] ] > max)
             {
                        max = v[ deque[front] ];
                        start = i - k + 1;
                        end = i;
             }
             if(deque[front] < i - k + 2) front++;
    }
    printf("%i %i %i", start, end, max);
    return 0;
}