Cod sursa(job #215335)

Utilizator mika17Mihai Alex Ionescu mika17 Data 18 octombrie 2008 14:40:54
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <deque>

#define NMAX 500001
#define BOUND 30001

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

int main()
{
 int N,K;

 freopen("secventa.in","r",stdin);
 scanf("%d %d",&N,&K);

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

 for(int i = 0, v ;i < N; ++i)
 {
        scanf("%d",&v);

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

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

        d[++dr].val = v; 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);
}