Cod sursa(job #215360)

Utilizator mika17Mihai Alex Ionescu mika17 Data 18 octombrie 2008 15:27:27
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>

#define NMAX 500001
#define BOUND 30001
#define BUF_MAX 3500014

struct deque {int val,pos; } d[NMAX];

int N,K,v[NMAX];

void read_parse()
{
 char b[BUF_MAX];

 freopen("secventa.in","r",stdin);

 scanf("%d%d",&N,&K);

 int buf_siz = fread(b,sizeof(char),BUF_MAX,stdin);

 for(int i = 0, k = 0, semn; i < buf_siz; ++i)
 {
  if( b[i] == '-' ) semn = 1;
   else
    if(b[i] <= '9' & b[i] >= '0')
      v[k] = v[k] * 10 + b[i] - '0';
     else
      if(b[i] == ' ') { v[k++] = semn ? v[k] * -1 : v[k] ; semn = 0; }
 }
}

int main()
{

 read_parse();

 //deque d[NMAX]; prea mare ca sa fie declarat in functie
 int max = -BOUND, st = 0, dr = -1, l, r;

 for(int i = 0 ;i < N; ++i)
 {
        if(st<=dr) {
        
                if(i >= K && d[st].pos == i - K)     //pop front
                 ++st;

                while(st<=dr && d[dr].val >= v[i])     //pop back
                 --dr;
        }

        d[++dr].val = v[i]; d[dr].pos = i;        //push back

        if(i >= K - 1 && d[st].val > max)
         max = d[st].val, l = i - K + 1, r = i;
 }
 freopen("secventa.out","w",stdout);
 printf("%d %d %d",l + 1, r + 1,max);
}