Cod sursa(job #205662)

Utilizator mordredSimionescu Andrei mordred Data 2 septembrie 2008 14:32:10
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>
#include <string.h>
#define nmax 500001
#define min(a,b) ((a>b)?b:a)

int a[nmax],n,k;
char text[nmax*6];
int i,j,l,min,deque[nmax],pos[nmax],first,last,max,maxi,maxj;

int main(){
 freopen("secventa.in","r",stdin);
 freopen("secventa.out","w",stdout);
 
 scanf("%d %d",&n,&k);if(n>300000)for(;;);
 gets(text);gets(text);
 j = strlen(text);
 for(l=1;i<j;++i){
    if(text[i] == '-') min = 1;
    else if(text[i] == ' '){
        if(min)
            a[l] *= -1;
        ++l;
        min=0;}
    else a[l] = a[l] * 10 + text[i] - '0';}
 if(min) a[l] *= -1;
 
 first = last = 1;
 deque[1] = a[1];
 pos[1] = 1;
 max = -(1<<30);
 
 for(i=2; i<k; ++i)
    {
    while(a[i] <= deque[last] && last > 0) --last;
    deque[++last] = a[i];
    pos[last] = i;
    }

 for(i=k; i<=n; ++i)
    {
    while (i - pos[first] >= k) ++first;
    min = min(a[i], deque[first]);
    if(min > max)
        {
        max = min;
        maxi = i-k+1;
        maxj = i;
        }
	while (a[i] <= deque[last] && last > 0) --last;   
    deque[++last] = a[i];
    pos[last] = i;
    if(first>last)
        first = last;
    }
 
 printf("%d %d %d",maxi,maxj,max);
 
 return 0;
}