Cod sursa(job #139802)

Utilizator ConsstantinTabacu Raul Consstantin Data 20 februarie 2008 18:16:38
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>     
#include <string.h>     
#include <stdlib.h>     
#define nr 500004

int n,k,i,A[nr],l1,l2,u,V[nr],P[nr],max,a,b,l;

char S[nr<<3];

int main(){
    max = -32000;                     
    freopen("secventa.in", "r", stdin);     
    freopen("secventa.out", "w", stdout);  
    scanf("%d %d\n", &n, &k);                
    gets(S);                                 
    A[1] = atoi(strtok(S, " \n"));           
    for (i = 2; i <= n; i++)     
        A[i] = atoi(strtok(NULL, " \n"));    
   for (i = 1, l1 = 0, l2 = -1, u=0;i<=n-k+1;i++){     
        while (u < i+k-1 && u <n) {     
            u++;                             
            while (l2 >=l1&& V[l2] >= A[u])     
                l2--;                         
            l2++;                             
            V[l2] = A[u];     
            P[l2] = u;     
        }                                      
	while (P[l1] < i)
            l1++;                          
        if (V[l1] > max){     
            max = V[l1];     
            a=i;     
            b= i+k-1;        
        }                       
     }                           
     printf("%d %d %d\n",a, b, max);
     return 0;
 }