Cod sursa(job #170846)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 3 aprilie 2008 12:39:58
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<stdio.h>
#define MAXN 500001

long pA,pB,REZ,N,U,L,V[MAXN],deque[MAXN];
long poz[MAXN],X[MAXN],query[MAXN];

void citesteDate(){
     int i;
     freopen("secventa.in","r",stdin);
     scanf("%ld %ld",&N,&L);

     for (i=1;i<=N;i++)
         scanf("%ld ",&V[i]);
}

void proceseaza(){
     long i,j,s1=1,s2=1;
     for (i=1;i<=N;i++){
         while (s1<=s2 && deque[s2]>V[i]) s2--;
         s2++;
         deque[s2]=V[i];
         poz[s2]=i;
         while (s1<=s2 && i-poz[s1]+1>=L) s1++;
         s1--;
         query[i]=poz[s1];
         if (REZ<deque[s1]){REZ=deque[s1];pA=poz[s1];pB=poz[s2];}
    }
}

void afiseazaRez(){
     freopen("secventa.out","w",stdout);
     printf("%ld %ld %ld\n",pA,pB,REZ);
}

int main(){
    citesteDate();
    proceseaza();
    afiseazaRez();
return 0;
}