Cod sursa(job #266284)

Utilizator Sorin_IonutBYSorynyos Sorin_Ionut Data 25 februarie 2009 10:33:34
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 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[1<<22];
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);
 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;
}