Cod sursa(job #205654)

Utilizator mordredSimionescu Andrei mordred Data 2 septembrie 2008 13:56:41
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 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,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(k=1;i<j;++i){
    if(text[i] == '-') min = 1;
    else if(text[i] == ' '){
        if(min)
            a[k] *= -1;
        ++k;
        min=0;}
    else a[k] = a[k] * 10 + text[i] - '0';}
 if(min) a[k] *= -1;
 
 first = last = 1;
 deque[1] = a[1];
 pos[1] = 1;
 min = -(1<<30);
 
 for(i=2; i<k; ++i)
    {
    while(a[i] <= deque[last] && last > 0) --last;
    deque[++last] = a[i];
    pos[last] = i;//for(j=first;j<=last;++j)printf("(%d,%d) ",deque[j],pos[j]);printf("\n");
    }
    
 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;//for(j=first;j<=last;++j)printf("(%d,%d) ",deque[j],pos[j]);printf("\n");
    }
 
 printf("%d %d %d",maxi,maxj,max);
 
 return 0;
}